1524. Number of Sub-arrays With Odd Sum
- Array
- Math
- Dynamic Programming
- Prefix Sum
TIME
O(n)
SPACE
O(1)
Intuition
With prefix sums P, the subarray arr[i..j-1] sums to P[j] - P[i]. A difference is odd exactly when the two numbers have different parities. So only the parity of each prefix sum matters, not its value.
For each end j, the number of odd subarrays ending there is the number of earlier prefixes (including the empty one, P[0] = 0) whose parity differs from P[j]. Two counters are enough.
Approach
- Start with
even = 1(the empty prefix) andodd = 0, andparity = 0. - For each
x: flipparityifxis odd.- If
parityis odd, every even prefix so far starts an odd subarray ending here:ans += even, thenodd += 1. - Otherwise
ans += odd, theneven += 1.
- If
- Return
ans % (10^9 + 7).
Complexity
- Time: O(n)
- Space: O(1)
Edge Cases
- All even values (example 2): every prefix is even,
oddstays 0, answer 0 - All odd values: parities alternate, so roughly half of all subarrays are odd
- A single element: 1 if it is odd, else 0
- The empty prefix must be counted as even; without it, subarrays starting at index 0 are missed (in
[1]the answer would be 0 instead of 1) - The raw count reaches about
n^2 / 4 ≈ 2.5 * 10^9for alternating parity, pastint, so Java accumulates inlongand takes the modulo once at the end
Code
class Solution:
def numOfSubarrays(self, arr: list[int]) -> int:
"""
1524. Number of Sub-arrays With Odd Sum
Time: O(n)
Space: O(1)
"""
MOD = 10**9 + 7
# Prefix sums seen so far, by parity. The empty prefix (sum 0) is even.
even, odd = 1, 0
parity = 0
ans = 0
for x in arr:
parity ^= x & 1
# A subarray ending here is odd iff its start prefix has the
# opposite parity to the current one.
if parity:
ans += even
odd += 1
else:
ans += odd
even += 1
return ans % MOD/**
* 1524. Number of Sub-arrays With Odd Sum
* Time: O(n)
* Space: O(1)
*/
class Solution {
public int numOfSubarrays(int[] arr) {
final int MOD = 1_000_000_007;
// Prefix sums seen so far, by parity. The empty prefix (sum 0) is even.
int even = 1, odd = 0;
int parity = 0;
// The count is (odd prefixes) * (even prefixes), at most about (n+1)^2 / 4
// ≈ 2.5 * 10^9, which overflows int but not long.
long ans = 0;
for (int x : arr) {
parity ^= x & 1;
// A subarray ending here is odd iff its start prefix has the
// opposite parity to the current one.
if (parity == 1) {
ans += even;
odd++;
} else {
ans += odd;
even++;
}
}
return (int) (ans % MOD);
}
}