1524: Number-of-Sub-arrays-With-Odd-Sum
Medium

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:

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:

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