Number of Sub-arrays With Odd Sum

How it works

We only need to track the parity of the prefix sum (0 for even, 1 for odd). A count array of size 2 stores how many prefix sums of each parity we have seen. For each new element, we look up the count of the opposite parity to find valid subarrays.

Steps

1. Initialize count[0] = 1 to represent the empty prefix (sum 0, which is even).
2. For each element, toggle the prefix parity by adding the element modulo 2.
3. Add count[1 - prefix] to the result (subarrays ending here with odd sum).
4. Increment count[prefix] and continue.
5. Return the final result.

Complexity

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

Things to watch for

Forgetting to Initialize Even Count

When using the prefix sum approach, the empty prefix (sum of zero elements) has an even sum. If you forget to initialize count[0] = 1 or evenCnt = 0 with proper handling, you will miss subarrays that start from index 0.

Confusing Parity Logic

The key insight is that odd - even = odd and even - odd = odd. Some programmers mistakenly check if the current prefix sum is odd and then add the count of odd prefix sums, when they should be adding the count of even prefix sums (since subtracting an even prefix from an odd prefix yields an odd subarray sum).

Not Applying Modulo Correctly

The result can grow very large, so modulo 10^9 + 7 must be applied. A common mistake is applying modulo only at the end instead of during each addition, which can cause integer overflow in languages without arbitrary precision integers.

from typing import List

class Solution:
    def numOfSubarrays(self, arr: List[int]) -> int:
        count = [1, 0]
        prefix = res = 0
        MOD = 10**9 + 7

        for num in arr:
            prefix = (prefix + num) % 2
            res = (res + count[1 - prefix]) % MOD
            count[prefix] += 1

        return res

class Solution {
public:
    int numOfSubarrays(vector<int>& arr) {
        int count[2] = {1, 0};
        int prefix = 0, res = 0;
        const int MOD = 1e9 + 7;

        for (int num : arr) {
            prefix = (prefix + num) % 2;
            res = (res + count[1 - prefix]) % MOD;
            count[prefix]++;
        }

        return res;
    }
};