1524. Number of Sub-arrays With Odd Sum - Explanation

1. Brute Force

Intuition

For each possible subarray, compute its sum and check if it is odd. We try every starting index and extend to every possible ending index, accumulating the sum incrementally.

Algorithm

For each starting index i, initialize a running sum.
Extend the subarray by adding elements one at a time up to index n-1.
After each addition, check if the current sum is odd and increment res if so.
Return the total count modulo 10^9 + 7.

class Solution:
    def numOfSubarrays(self, arr: List[int]) -> int:
        n, res = len(arr), 0
        mod = int(1e9 + 7)

        for i in range(n):
            curSum = 0
            for j in range(i, n):
                curSum += arr[j]
                if curSum % 2:
                    res = (res + 1) % mod

        return res

Time & Space Complexity

Time complexity: $O(n ^ 2)$
Space complexity: $O(1)$

2. Dynamic Programming (Top-Down)

Intuition

We use memoization to count subarrays ending at each position. For a subarray starting at index i, the parity of its sum depends on the running parity as we extend rightward. By caching results for each (index, parity) state, we avoid redundant calculations.

Algorithm

Define dfs(i, parity) returning the count of odd-sum subarrays starting at index i with the given running parity.
At each step, update the parity by adding the current element modulo 2.
Add 1 to the count if the new parity is odd, then recurse to the next index.
Sum up dfs(i, 0) for all starting indices to get the total.

class Solution:
    def numOfSubarrays(self, arr: List[int]) -> int:
        mod = 10**9 + 7
        n = len(arr)
        memo = {}

        def dp(i: int, parity: int) -> int:
            if i == n:
                return 0

            if (i, parity) in memo:
                return memo[(i, parity)]

            new_parity = (parity + arr[i]) % 2
            res = new_parity + dp(i + 1, new_parity)
            memo[(i, parity)] = res % mod
            return memo[(i, parity)]

        ans = 0
        for i in range(n):
            ans = (ans + dp(i, 0)) % mod

        return ans

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$

3. Dynamic Programming (Bottom-Up)

Intuition

We can convert the top-down approach to bottom-up by processing indices from right to left. For each position, we compute how many odd-sum subarrays can be formed starting there, given either even or odd running parity.

Algorithm

Create a 2D array dp[i][parity] representing counts from index i with given parity.
Iterate from the last index to the first.
For each parity, compute the new parity after including the current element and fill in the dp value.
Sum dp[i][0] for all indices to get the final answer.

class Solution:
    def numOfSubarrays(self, arr: List[int]) -> int:
        n = len(arr)
        mod = 10**9 + 7
        dp = [[0] * 2 for _ in range(n + 1)]

        for i in range(n - 1, -1, -1):
            for parity in range(2):
                new_parity = (parity + arr[i]) % 2
                dp[i][parity] = (new_parity + dp[i + 1][new_parity]) % mod

        res = 0
        for i in range(n):
            res = (res + dp[i][0]) % mod
        return res

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$

4. Prefix Sum - I

Intuition

A subarray has an odd sum when its prefix sum parity differs from the prefix sum at its starting point. If the current prefix sum is odd, pairing it with any previous even prefix sum yields an odd subarray. We track counts of odd and even prefix sums seen so far.

Algorithm

Maintain counters for odd and even prefix sums encountered.
For each element, update the running prefix sum.
If the prefix sum is odd, add 1 (for the subarray from the start) plus the count of previous even prefix sums.
If even, add the count of previous odd prefix sums.
Update the appropriate counter and return res.

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

        for n in arr:
            cur_sum += n
            if cur_sum % 2:
                res = (res + 1 + even_cnt) % MOD
                odd_cnt += 1
            else:
                res = (res + odd_cnt) % MOD
                even_cnt += 1

        return res

Time & Space Complexity

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

5. Prefix Sum - II

Intuition

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.

Algorithm

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

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

Time & Space Complexity

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

Common Pitfalls

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.