Number of Sub-arrays With Odd Sum — Algorithms&Visualizations

In this article, we are going to talk about an interesting challenge I’ve recently got to solve. Instead of providing right away the final algorithm that I came up with, I’ll be trying to explain the whole thought process that led me to the final solution. Let’s get started!

The Problem
The first time I ran into this challenge, I was taking a coding contest on LeetCode. The problem is titled Number of Sub-arrays With Odd Sum, let’s check this out:

Given an array of integers arr. Return the number of sub-arrays with odd sum.

As the answer may grow large, the answer must be computed modulo 10^9 + 7.

Example:
Input: arr = [1, 2, 3, 4, 5]
Output: 9

As a matter of fact, the sub-arrays with odd sum are:
[1], [3], [5], [1, 2], [2, 3], [3, 4], [4, 5], [2, 3, 4], [1, 2, 3, 4, 5]

The problem is rather clear and it doesn't need any extra explanations. Everything is settled to start crafting our solution.

First approach
I have got to be honest with you, it wasn’t the first time that I faced a problem involving sub-arrays or sub-strings. Having a template that I use when it comes to working on these kinds of problems, that was the main driver of my first attempt. Let show you:

Template
1. Loop over the array elements and for each element in the given array:

2. Push the element into Sub-arrays (blue rectangle)

3. Push the element into Recently Added Sub-Arrays (orange rectangle)

4. Push into the Sub-arrays(blue rectangle) all the elements in the Previous step Added Sub-arrays (green rectangle) adding the element to each of them

5. Copy the Recently Added Sub-arrays elements into the Previous Step Added Sub-arrays

6. Repeat

When an element gets added to Sub-arrays (the blue rectangle), we can easily compute the sum and check if it is odd or even. Although the approach is correct, it will produce Time Limited Exceeded exceptions when you run it against very long input arrays.
The algorithm needs to copy all of the elements in Recently Added Sub-arrays into the Previous step Added Sub-arrays. Probably we need to figure out a way to avoid that step.

Second Approach
The previous attempt didn’t work out, I need to figure out how to compute step by step the number of subarrays with even and odd total sum of the elements. Let’s start with a trivial observation:
Even + Even = Even (10 + 6 = 16)
Even + Odd = Odd (10 + 5 = 15)
Odd + Odd = Even (5 + 5 = 10)

I know this taken for granted, but let’s have a look at how we can use this information to improve the previous algorithm by ditching the arrays copy procedure at each step:

1. Loop over the elements of the input Array.
   At each step:
2. If the element is odd, add +1 to Recently Added Odd Sums (orange rectangle on top). It represents the element itself.
   If the element is even, add +1 to Recently Added Even Sums (orange rectangle on the bottom).

3. If the element is odd:
(a) Add Previous step Added Even Sums to Recently Added Odd Sums
(b) Add Previous step Added Odd Sums to Recently Added Even Sums
If element id Even
(a) Add Previous step Added Even Sums to Recently Added Even Sum
(b) Add Previous step Added Odd Sums to Recently Added Odd Sums

4. Add Recently Added Odd Sums to Result (blue rectangle)

5. Repeat from point 2.

Do you see what I am doing here? Even if the pictures show the Sums for sake of clarity, it’s irrelevant what they are. Think about it! I don’t care if Recently Added Odd Sums=2 refers to [[9],[7]] or to [[3],[5]], because that’s irrelevant. The only crucial aspect is that there are 2 odd sums, that it!
When the next element is even, whatever the Previously Added Odd Sums are, added to an odd sum will give another odd sum (Odd + Even = Odd). On the other hand, if added to the Previously Added Even Sums, it will give odd results. If you are not convinced, check this out

Element = 2
Previously Added Even Sums = 3
Previously Added Odd Sums = 2

Do you really need to know what are the elements Previously added? If you think so, no worries, let me give you the elements then:

Element = 2
Previously Added Even Sums = 3 {[6],[4],[8]}
Previously Added Odd Sums = 2 {[10001],[9]}

Can you tell me now how many Odd sums and Even sums will you get by adding Element 2 to the different sums? Easy no:

Element = 2
Recently Added Even Sums = 4 {[6+2],[4+2], [8+2]} + {[2]}
Recently Added Odd Sums = 2 {[1001+2],[9+2]}

Ok, now repeat the procedure, but replace the Sums with whatever you like the most. Can you see that now? It doesn’t matter what the Sums are, as long as you add an even number to an even sum, you always obtain another even Sum, and if you add it to an odd sum, that stays odd. That’s it!
The bottom line is that we don’t really need to know what are the Sums, but just if they are Even or Odd.

Code

Conclusion
I hope you enjoyed this article and learned something new. Have a great day!

“Nature is wise. You can learn everywhere and from everything.”
— Leonardo da Vinci