Number of Sub-arrays With Odd Sum solution and explanation
Google
9 more videos on this problem
Number of Sub-arrays With Odd Sum - Leetcode 1524 - PythonNeetCodeIO · 13:01 · 15K views
Number of Sub-arrays With Odd Sum | Brute Force | Better | Optimal | Leetcode 1524 |codestorywithMIKcodestorywithMIK · 31:46 · 11K views
Number of Subarrays With Odd Sum | Leetcode 1524Techdose · 13:34 · 7K views
Number of Sub-arrays With Odd Sum (Leetcode 1524)Coding Interviews · 19:06 · 5K views
1524. Number of Sub-arrays With Odd Sum | Prefix Sums | ArraysAryan Mittal · 13:54 · 3K views
1524. Number of Sub-arrays With Odd Sum | leetcode daily challenge | dsa | faang | shashcodeShashCode · 7:36 · 3K views
1524. Number of Sub-arrays With Odd Sum (Leetcode Medium)Programming Live with Larry · 7:40 · 2K views
Number of Sub-arrays With Odd Sum (Leetcode 1524)Algorithms Casts · 31:06 · 1K views
Leetcode 1524. Number of Sub-arrays With Odd SumElite Code · 23:39 · 1K views
Number of Sub arrays With Odd Sum || LeetCode || 1524 || Dynamic ProgrammingPerceiver · 14:58 · 817 views
The problem
Given an array of integers arr, return the number of subarrays with an odd sum.
Since the answer can be very large, return it modulo 109 + 7.
Example 1:
Input: arr = [1,3,5] Output: 4 Explanation: All subarrays are [[1],[1,3],[1,3,5],[3],[3,5],[5]] All sub-arrays sum are [1,4,9,3,8,5]. Odd sums are [1,9,3,5] so the answer is 4.
Example 2:
Input: arr = [2,4,6] Output: 0 Explanation: All subarrays are [[2],[2,4],[2,4,6],[4],[4,6],[6]] All sub-arrays sum are [2,6,12,4,10,6]. All sub-arrays have even sum and the answer is 0.
Example 3:
Input: arr = [1,2,3,4,5,6,7] Output: 16
Constraints:
1 <= arr.length <= 1051 <= arr[i] <= 100
Approach overview
Problem Overview: Given an integer array arr, count how many subarrays have an odd total sum. A subarray is any contiguous portion of the array. The challenge is identifying odd sums efficiently without recomputing the sum for every possible subarray.
Approach 1: Brute Force Enumeration (O(n²) time, O(1) space)
Check every possible subarray. Use two nested loops: the outer loop selects the start index, and the inner loop expands the end index while maintaining a running sum. Each time the sum becomes odd, increment the result counter. This approach is easy to implement and demonstrates understanding of the problem, but it performs up to n² sum updates, which becomes slow for large arrays.
Approach 2: Parity-based Counting with Prefix Sums (O(n) time, O(1) space)
This method relies on prefix sums and the observation that an odd sum occurs when one prefix sum is even and the other is odd. Track the parity of the running prefix sum using sum % 2. Maintain two counters: how many prefixes so far are even and how many are odd. When the current prefix is odd, every previous even prefix forms an odd subarray. When the current prefix is even, every previous odd prefix forms an odd subarray. The algorithm iterates through the array once, updating counts and accumulating the answer. This pattern appears frequently in array problems that involve parity or prefix properties.
Approach 3: Direct Calculation with Sliding Window Insight (O(n) time, O(1) space)
Another way to reason about the problem is by tracking how many odd numbers appear as you scan the array. Each time the running prefix becomes odd, you know the current index can form odd-sum subarrays with previous even prefixes. Instead of storing full prefix values, you keep counts of odd and even states and update the result during iteration. Conceptually this resembles a sliding accumulation across the array where contributions are added as the window expands. It avoids nested loops and uses only constant memory.
Recommended for interviews: The parity-based prefix sum approach is the expected solution. Interviewers want to see recognition that odd sums depend on parity differences between prefix sums. Starting with the brute force method shows baseline reasoning, but converting the idea into an O(n) counting strategy demonstrates strong understanding of dynamic programming style prefix states and prefix sum optimization.
Approach 1: Parity-based Counting with Prefix Sums
We can use the properties of odd and even sums in combination with prefix sums to efficiently count subarrays with odd sums. The idea is to traverse the array while maintaining two counts: the count of prefix sums that are currently odd and the count of prefix sums that are even. A prefix sum ending in an odd count can be paired with a previous prefix sum ending in an even count to form an odd sum subarray. Each time a prefix sum is computed, we determine its parity and update our counters accordingly. The result is the sum of the count of odd prefix sums already found when a new odd prefix sum is encountered.
def numOfSubarrays(arr):
MOD = 10**9 + 7
odd, even = 0, 1
total_odd, prefix_sum = 0, 0
for num in arr:
prefix_sum += num
if prefix_sum % 2 == 1:
total_odd += even
odd += 1
else:
total_odd += odd
even += 1
return total_odd % MODclass Solution {
public int numOfSubarrays(int[] arr) {
final int MOD = 1000000007;
int odd = 0, even = 1, totalOdd = 0, prefixSum = 0;
for (int num : arr) {
prefixSum += num;
if (prefixSum % 2 == 1) {
totalOdd = (totalOdd + even) % MOD;
odd++;
} else {
totalOdd = (totalOdd + odd) % MOD;
even++;
}
}
return totalOdd;
}
}#include <vector>
using namespace std;
int numOfSubarrays(vector<int>& arr) {
const int MOD = 1e9 + 7;
int odd = 0, even = 1, total_odd = 0, prefix_sum = 0;
for (int num : arr) {
prefix_sum += num;
if (prefix_sum % 2 == 1) {
total_odd = (total_odd + even) % MOD;
odd++;
} else {
total_odd = (total_odd + odd) % MOD;
even++;
}
}
return total_odd;
}var numOfSubarrays = function(arr) {
const MOD = 1e9 + 7;
let odd = 0, even = 1, totalOdd = 0, prefixSum = 0;
for (let num of arr) {
prefixSum += num;
if (prefixSum % 2 === 1) {
totalOdd = (totalOdd + even) % MOD;
odd++;
} else {
totalOdd = (totalOdd + odd) % MOD;
even++;
}
}
return totalOdd;
};#include <stdio.h>
#define MOD 1000000007
int numOfSubarrays(int* arr, int arrSize){
int odd = 0, even = 1, total_odd = 0, prefix_sum = 0;
for (int i = 0; i < arrSize; ++i) {
prefix_sum += arr[i];
if (prefix_sum % 2 == 1) {
total_odd = (total_odd + even) % MOD;
odd++;
} else {
total_odd = (total_odd + odd) % MOD;
even++;
}
}
return total_odd;
}public class Solution {
public int NumOfSubarrays(int[] arr) {
const int MOD = 1000000007;
int odd = 0, even = 1, totalOdd = 0, prefixSum = 0;
foreach (int num in arr) {
prefixSum += num;
if (prefixSum % 2 == 1) {
totalOdd = (totalOdd + even) % MOD;
odd++;
} else {
totalOdd = (totalOdd + odd) % MOD;
even++;
}
}
return totalOdd;
}
}The function iteratively computes the prefix sum while maintaining counts of how many times odd and even prefix sums have been encountered. For each element, it computes whether the current prefix sum is odd or even and updates the number of subarrays found with odd sums accordingly.
Time Complexity: O(n), as the solution traverses the array in a single pass.
Space Complexity: O(1), since it uses a fixed amount of additional memory.
Approach 2: Direct Calculation with Sliding Window
A more intuitive but less efficient approach involves checking every possible subarray sum directly by iterating through all possible start and end indices using a nested loop. For each subarray, calculate the sum and count it if it's odd. This approach serves as a good educational step to understand the problem before optimizing with other methods.
def numOfSubarrays(arr):
MOD = 10**9 + 7
n = len(arr)
count = 0
for start in range(n):
total = 0
for end in range(start, n):
total += arr[end]
if total % 2 == 1:
count += 1
return count % MODclass Solution {
public int numOfSubarrays(int[] arr) {
final int MOD = 1000000007;
int count = 0;
int n = arr.length;
for (int start = 0; start < n; ++start) {
int total = 0;
for (int end = start; end < n; ++end) {
total += arr[end];
if (total % 2 == 1) {
count = (count + 1) % MOD;
}
}
}
return count;
}
}#include <vector>
using namespace std;
int numOfSubarrays(vector<int>& arr) {
const int MOD = 1e9 + 7;
int n = arr.size();
int count = 0;
for (int start = 0; start < n; ++start) {
int total = 0;
for (int end = start; end < n; ++end) {
total += arr[end];
if (total % 2 == 1) {
count = (count + 1) % MOD;
}
}
}
return count;
}var numOfSubarrays = function(arr) {
const MOD = 1e9 + 7;
let count = 0;
for (let start = 0; start < arr.length; ++start) {
let total = 0;
for (let end = start; end < arr.length; ++end) {
total += arr[end];
if (total % 2 === 1) {
count = (count + 1) % MOD;
}
}
}
return count;
};#include <stdio.h>
int numOfSubarrays(int* arr, int arrSize){
const int MOD = 1000000007;
int count = 0;
for (int start = 0; start < arrSize; ++start) {
int total = 0;
for (int end = start; end < arrSize; ++end) {
total += arr[end];
if (total % 2 == 1) {
count = (count + 1) % MOD;
}
}
}
return count;
}public class Solution {
public int NumOfSubarrays(int[] arr) {
const int MOD = 1000000007;
int count = 0;
int n = arr.Length;
for (int start = 0; start < n; ++start) {
int total = 0;
for (int end = start; end < n; ++end) {
total += arr[end];
if (total % 2 == 1) {
count = (count + 1) % MOD;
}
}
}
return count;
}
}This nested loop approach iterates over every possible subarray, calculating their sums, and counts those with an odd sum.
Time Complexity: O(n^2), because it sums every possible subarray.
Space Complexity: O(1).
Approach 3: Prefix Sum + Counter
We define an array cnt of length 2 as a counter, where cnt[0] and cnt[1] represent the number of subarrays with even and odd prefix sums, respectively. Initially, cnt[0] = 1 and cnt[1] = 0.
Next, we maintain the current prefix sum s, initially s = 0.
Traverse the array arr, for each element x encountered, add the value of x to s, then based on the parity of s, add the value of cnt[s \mod 2 \oplus 1] to the answer, and then increment the value of cnt[s \mod 2] by 1.
After the traversal, we get the answer. Note the modulo operation for the answer.
Time complexity is O(n), where n is the length of the array arr. Space complexity is O(1).
function numOfSubarrays(arr: number[]): number {
let ans = 0;
let s = 0;
const cnt: number[] = [1, 0];
const mod = 1e9 + 7;
for (const x of arr) {
s += x;
ans = (ans + cnt[(s & 1) ^ 1]) % mod;
cnt[s & 1]++;
}
return ans;
}func numOfSubarrays(arr []int) (ans int) {
const mod int = 1e9 + 7
cnt := [2]int{1, 0}
s := 0
for _, x := range arr {
s += x
ans = (ans + cnt[s&1^1]) % mod
cnt[s&1]++
}
return
}impl Solution {
pub fn num_of_subarrays(arr: Vec<i32>) -> i32 {
const MOD: i32 = 1_000_000_007;
let mut cnt = [1, 0];
let mut ans = 0;
let mut s = 0;
for &x in arr.iter() {
s += x;
ans = (ans + cnt[((s & 1) ^ 1) as usize]) % MOD;
cnt[(s & 1) as usize] += 1;
}
ans
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Parity-based Counting with Prefix Sums | Time Complexity: O(n), as the solution traverses the array in a single pass. |
| Direct Calculation with Sliding Window | Time Complexity: O(n^2), because it sums every possible subarray. |
| Prefix Sum + Counter | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Enumeration | O(n²) | O(1) | Small arrays or when demonstrating baseline reasoning before optimizing |
| Parity-based Prefix Sum Counting | O(n) | O(1) | General case; optimal solution expected in interviews |
| Direct Calculation with Sliding Window Insight | O(n) | O(1) | When reasoning about odd/even transitions during a single pass |
Frequently asked questions
Is Number of Sub-arrays With Odd Sum easy or hard?
The problem is rated Medium because the brute force idea is straightforward but the optimal solution requires recognizing a prefix sum parity pattern. Once the odd-even prefix relationship is identified, the algorithm becomes a simple O(n) counting pass.
Number of Sub-arrays With Odd Sum Python/Java solution
In Python or Java, compute a running prefix sum and track parity using sum % 2. Maintain two variables counting even and odd prefixes and update the answer accordingly during iteration. The implementation is short and runs in O(n) time with constant space.
How to solve Number of Sub-arrays With Odd Sum in O(n)?
Maintain a running prefix sum and track whether it is even or odd. Keep two counters: number of even prefixes and number of odd prefixes seen so far. If the current prefix is odd, add the count of even prefixes to the answer; if it is even, add the count of odd prefixes. Update the prefix counters as you iterate through the array.
What is the best approach for Number of Sub-arrays With Odd Sum?
The optimal approach uses prefix sum parity counting. Track how many prefix sums are even and odd while iterating through the array. An odd subarray occurs whenever the current prefix parity differs from a previous prefix parity. This method runs in O(n) time and uses O(1) extra space.
Is Number of Sub-arrays With Odd Sum asked at Google/Amazon/Meta?
Variants of prefix sum parity problems appear frequently in interviews at companies like Amazon, Google, and Meta. Interviewers use them to evaluate understanding of prefix sums, parity properties, and how to transform a quadratic enumeration into a linear counting problem.
What data structure is used in Number of Sub-arrays With Odd Sum?
The solution mainly relies on prefix sums and simple counters for odd and even parity states. No complex data structures are required—just integer variables that track counts while iterating through the array.
What is the time complexity of Number of Sub-arrays With Odd Sum?
The optimal solution runs in O(n) time because the array is scanned once while maintaining counts of even and odd prefix sums. A brute force approach that checks every subarray takes O(n^2) time, which is significantly slower for large inputs.