Number of Sub-arrays With Odd Sum

Medium
1137.

Number of Sub-arrays With Odd Sum

Number of Sub-arrays With Odd Sum is a medium coding problem on arrays, dynamic programming and math, asked in Amazon and Directi interviews.

Given an array of positive integers arr, count its non-empty contiguous subarrays whose sum is odd.

The count can be large, so return it modulo 10^9 + 7.

Example 1

Input
arr = [1,2,3,4]
Output
6
Explanation
`[1]`, `[1,2]`, `[2,3]`, `[2,3,4]`, `[3]` and `[3,4]`.

Example 2

Input
arr = [2,4,6]
Output
0

Example 3

Input
arr = [7]
Output
1

Constraints

  • 1 <= arr.length <= 10^5
  • 1 <= arr[i] <= 100
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} arr
 * @return {number}
 */
var numOfSubarrays = function(arr) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Number of Sub-arrays With Odd Sum — Problem & Solution

Number of Sub-arrays With Odd Sum solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Number of Sub-arrays With Odd Sum is a medium coding problem on arrays, dynamic programming and math, asked in Amazon and Directi interviews.

Problem statement

Given an array of positive integers arr, count its non-empty contiguous subarrays whose sum is odd.

The count can be large, so return it modulo 10^9 + 7.

Example 1

Input: arr = [1,2,3,4]
Output: 6
Explanation: `[1]`, `[1,2]`, `[2,3]`, `[2,3,4]`, `[3]` and `[3,4]`.

Example 2

Input: arr = [2,4,6]
Output: 0

Example 3

Input: arr = [7]
Output: 1

Constraints

  • 1 <= arr.length <= 10^5
  • 1 <= arr[i] <= 100

Hints for Number of Sub-arrays With Odd Sum

  1. Hint 1

    A subarray sum is a difference of two prefix sums.

  2. Hint 2

    The difference of two integers is odd exactly when one is odd and the other is even.

  3. Hint 3

    Walk the prefix sums keeping how many so far were even (the empty prefix counts as even) and how many were odd; each new prefix pairs with all earlier prefixes of the opposite parity.

How to solve Number of Sub-arrays With Odd Sum

Subarray arr[l..r] has sum P[r+1] - P[l], which is odd exactly when the two prefix sums have different parity — so count opposite-parity pairs of prefixes.

Approach

  1. Start with even = 1 (the empty prefix, sum 0) and odd = 0.
  2. Scan the array maintaining the parity of the running prefix sum.
  3. If the current prefix is odd, add even to the answer and increment odd; otherwise add odd and increment even.
  4. Keep the answer reduced modulo 10^9 + 7.

Why it works

Each subarray corresponds to exactly one pair of prefix positions l < r + 1, and its sum is odd iff those prefixes differ in parity. At step r the counters hold the parities of all earlier prefixes, so every odd-sum subarray ending at r is counted once.

Complexity

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

Pitfalls

  • Forgetting the empty prefix misses every odd subarray that starts at index 0.
  • Only parity matters — keeping full prefix sums is unnecessary.
  • The count is about n^2 / 4 at most, which overflows 32 bits for large n — reduce as you go.

Reference solution

Python

from typing import List

def numOfSubarrays(arr: List[int]) -> int:
    MOD = 10 ** 9 + 7
    even, odd = 1, 0
    parity = 0
    ans = 0
    for a in arr:
        parity ^= a & 1
        if parity:
            ans += even
            odd += 1
        else:
            ans += odd
            even += 1
    return ans % MOD

Java

public static int numOfSubarrays(int[] arr) {
    final int MOD = 1000000007;
    int even = 1, odd = 0, parity = 0, ans = 0;
    for (int a : arr) {
        parity ^= a & 1;
        if (parity == 1) {
            ans = (ans + even) % MOD;
            odd++;
        } else {
            ans = (ans + odd) % MOD;
            even++;
        }
    }
    return ans;
}

C++

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

JavaScript

var numOfSubarrays = function(arr) {
    var MOD = 1000000007;
    var even = 1, odd = 0, parity = 0, ans = 0;
    for (var i = 0; i < arr.length; i++) {
        parity ^= arr[i] & 1;
        if (parity === 1) {
            ans = (ans + even) % MOD;
            odd++;
        } else {
            ans = (ans + odd) % MOD;
            even++;
        }
    }
    return ans;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Dynamic Programming