Number of Sub-arrays With Odd Sum

medium array math dp prefix sum

Problem

Given an array of positive integers arr, return the number of subarrays with an odd sum. Because the answer can be very large, return it modulo 10^9 + 7.

Inputarr = [1, 3, 5]

Output4

Odd-sum subarrays: [1], [5], [1,3,5], [3,5].

arr (comma-separated)

def num_odd_sum_subarrays(arr):
    MOD = 10**9 + 7
    even, odd = 1, 0  # prefix-sum parity counts (empty prefix is even)
    s = 0; ans = 0
    for x in arr:
        s += x
        if s % 2 == 1:
            ans = (ans + even) % MOD
            odd += 1
        else:
            ans = (ans + odd) % MOD
            even += 1
    return ans

function numOfSubarrays(arr) {
  const MOD = 1000000007n;
  let even = 1n, odd = 0n;
  let s = 0, ans = 0n;
  for (const x of arr) {
    s += x;
    if (s % 2 === 1) { ans = (ans + even) % MOD; odd++; }
    else { ans = (ans + odd) % MOD; even++; }
  }
  return Number(ans);
}

class Solution {
    public int numOfSubarrays(int[] arr) {
        long MOD = 1_000_000_007L;
        long even = 1, odd = 0, s = 0, ans = 0;
        for (int x : arr) {
            s += x;
            if (s % 2 == 1) { ans = (ans + even) % MOD; odd++; }
            else { ans = (ans + odd) % MOD; even++; }
        }
        return (int) ans;
    }
}

int numOfSubarrays(vector<int>& arr) {
    const long MOD = 1000000007;
    long even = 1, odd = 0, s = 0, ans = 0;
    for (int x : arr) {
        s += x;
        if (s % 2 == 1) { ans = (ans + even) % MOD; odd++; }
        else { ans = (ans + odd) % MOD; even++; }
    }
    return (int) ans;
}

Explanation

A subarray's sum equals one prefix sum minus an earlier prefix sum. That difference is odd exactly when the two prefix sums have different parity — one even and one odd. So we don't care about the actual sums, only whether each running prefix is even or odd.

We sweep through the array keeping s, the running prefix sum, and two counters: even and odd, for how many prefix sums of each parity we have seen. The empty prefix counts as even, so we start with even = 1.

At each step, if the current prefix is odd, every earlier even prefix pairs with it to form an odd-sum subarray, so we add even to the answer and bump odd. If the current prefix is even, we add odd instead and bump even. Everything is kept modulo 10^9 + 7.

Example: arr = [1, 3, 5] gives prefix sums 1, 4, 9 (odd, even, odd). The odd-sum subarrays are [1], [5], [3,5], and [1,3,5] — exactly 4.

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