Number of Sub-arrays With Odd Sum

main.md

Question

Approach

I started by using two counters: even_count and odd_count. First, I set even_count to 1 to account for an empty prefix sum, and odd_count to 0. As I iterated through the array, I accumulated the prefix sum and checked whether it was odd or even. When the prefix sum was even, I added the odd_count to the result since combining an even prefix sum with a prior odd prefix would result in an odd subarray sum. Conversely, if the prefix sum was odd, I added the even_count to the result, on the fact that an odd prefix sum paired with a prior even prefix sum also yields an odd subarray sum.

To handle large outputs, I kept the result modulo (10^9 + 7) throughout the process.

Implementation

class Solution:
    def numOfSubarrays(self, arr: List[int]) -> int:
        MOD = 10**9 + 7
        odd_count = 0
        even_count = 1
        curr_sum = 0
        result = 0

        for num in arr:
            curr_sum += num
            if curr_sum % 2 == 0:
                result = (result + odd_count) % MOD
                even_count += 1
            else:
                result = (result + even_count) % MOD
                odd_count += 1

        return result

Complexities

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