Number of Sub arrays With Odd Sum

For this question, since we are dealing with subarrays, my first thought was to pre-generate a prefix array, allowing you to calculate the sum of any subarray in O(1) time. From the sum, we can then get the parity of it.

We can take this a step further, however, as the parity of the sum of the subarray depends only on the 2 prefix sum values that we choose (e.g. it will only be odd, if we choose 1 even and 1 odd prefix sum value).

Consequently, realise that we also do not even need to calculate the prefix sum at all; just keep track of the least-significant bit as it is the only bit that affects parity.

Therefore, we just need to keep track of 3 things:

• the number of even prefix sum values, e
• the number of odd prefix sum values, o
• the parity of the current prefix sum value, parity

Then, as we iterate through arr, we can xor our parity counter with the LSB of arr[i]. Then, using ans to track the number of subarrays with an odd sum:

• if parity == 0, we know the current prefix sum value is even, so subtracting any odd prefix sum values from it will generate a subarray with an odd sum
  • hence, we can do ans += o
• if parity == 1, we know the current prefix sum value is odd, so subtracting any even prefix sum values from it will generate a subarray with an odd sum
  • hence, we can do ans += e+1 (the +1 comes from the current prefix sum value itself as it is already odd)

Finally, remember to do ans %= int(1e9+7) as we have to return the answer modulo 10^9 + 7.

code

class Solution {
public:
    int numOfSubarrays(vector<int>& arr) {
        int o = 0;
        int e = 0;
        int parity = 0;
        int ans = 0;
        for (int &n : arr) {
            parity ^= (n&1);
            if (parity == 0) {
                ans += o;
                ++e;
            } else {
                ans += e+1;
                ++o;
            }
            ans %= int(1e9+7);
        }
        return ans;
    }
};

complexity

• Time: O(n)
• Space: O(1)