Number of Sub-arrays With Odd Sum

first, note that we can abstract all the numbers in the array as either even or odd, since only a number's parity decides whether a sum is odd. similarly, we can abstract every sub-array as either even or odd, depending on its sum.

then realise that for any array, e.g. [24, 18, 11, 6], if we were to add another number, e.g. 5, at the end of the array, then the new sub-arrays we have to account for are:

• [24, 18, 11, 6, 5]
• [18, 11, 6, 5]
• [11, 6, 5]
• [6, 5]
• [5]

these are just the old sub-arrays ending at 6, each with 5 added, plus [5] on its own. so we only need two counts:

• how many sub-arrays ending at the last number are odd (curr_odd),
• how many sub-arrays ending at the last number are even (curr_even).

for our previous example, before the 5, curr_odd is 3 and curr_even is 1.

adding a number, x, then only has two cases:

• an even number keeps every sum's parity, and [x] on its own is even, so curr_even goes up by 1.
• an odd number flips every sum's parity, so we swap the two counts, and [x] on its own is odd, so curr_odd goes up by 1.

therefore, since 5 is odd, the counts swap to 1 odd and 3 even, then [5] makes it 2 odd. finally, we add curr_odd to our running total, since those are exactly the new odd sub-arrays, and repeat for all the numbers inside arr.

code link to code#

class Solution {
public:
    int numOfSubarrays(vector<int>& arr) {
        long long total_odd{0};
        long long curr_odd{0}, curr_even{0};
        const long long MODULO{static_cast<long long>(1e9) + 7};

        for (int num : arr) {
            if (num % 2 == 1) {
                swap(curr_odd, curr_even);
                ++curr_odd;
            } else {
                ++curr_even;
            }
            total_odd = (total_odd + curr_odd) % MODULO;
        }

        return static_cast<int>(total_odd);
    }
};

complexity link to complexity#

• Time: O(n) where n = arr.size()
• Space: O(1)

time taken link to time taken#

• 12 minutes and 31 seconds