Number of Sub-arrays With Odd Sum

Number of Sub-arrays With Odd Sum

What is this problem about?

The Number of Sub-arrays With Odd Sum problem asks you to count subarrays whose sum is odd. This coding problem uses the prefix sum parity trick: a subarray sum is odd if and only if the parities of its two endpoint prefix sums differ. The array, math, dynamic programming, and prefix sum interview pattern is the core.

Why is this asked in interviews?

Microsoft, Meta, Amazon, Google, and Bloomberg ask this because it reduces a subarray counting problem to prefix parity counting — a clean O(n) approach. Candidates who see "odd sum subarray" should immediately think "prefix sum parity" and then count pairs of prefix sums with different parity.

Algorithmic pattern used

Prefix parity count. Track how many prefix sums so far have been even (even_count) and how many odd (odd_count). For each new prefix sum: if it's even, the number of subarrays ending here with odd sum = odd_count (pair with each previous odd prefix). If it's odd, it's even_count. Accumulate the answer. Apply mod 10^9+7.

Example explanation

arr=[1,3,5]. Prefix sums: 0,1,4,9.

• Prefix 0 (even): even_count=1, odd_count=0.
• Prefix 1 (odd): subarrays = even_count=1. ans=1. odd_count=1.
• Prefix 4 (even): subarrays = odd_count=1. ans=2. even_count=2.
• Prefix 9 (odd): subarrays = even_count=2. ans=4. odd_count=2. Answer = 4 (subarrays with odd sum: [1],[3],[5],[1,3,5] actually sum=9 odd. Let me check [3,5]=8 even. [1,3]=4 even. [1]=1 odd, [3]=3 odd, [5]=5 odd, [1,3,5]=9 odd. Count = 4 ✓).

Common mistakes candidates make

• Computing all prefix sums first then counting pairs (correct but less elegant than incremental approach).
• Using mod too late (overflow before applying mod).
• Not initializing even_count=1 (for the empty prefix sum = 0, which is even).
• Checking each subarray individually (O(n²)).

Interview preparation tip

Prefix sum parity problems are O(n) and based on the insight: odd - odd = even, even - even = even, odd - even = odd, even - odd = odd. So subarray sum is odd ⟺ prefix sums at endpoints have different parity. Count pairs of different-parity prefix sums incrementally as you scan. Practice this pattern for "count subarrays with sum divisible by k" — the same prefix-remainder hash map technique generalizes from parity (mod 2) to any modulus.