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.
- Difficulty: Medium
- Topics: Arrays, Dynamic Programming, Math, Prefix Sum
- Asked at: Amazon, Directi
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
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^51 <= arr[i] <= 100
Hints for Number of Sub-arrays With Odd Sum
Hint 1
A subarray sum is a difference of two prefix sums.
Hint 2
The difference of two integers is odd exactly when one is odd and the other is even.
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
- Start with
even = 1(the empty prefix, sum 0) andodd = 0. - Scan the array maintaining the parity of the running prefix sum.
- If the current prefix is odd, add
evento the answer and incrementodd; otherwise addoddand incrementeven. - 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 % MODJava
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