Number of Sub-arrays With Odd Sum - Solution & Explanation
Problem Statement
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.
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.
Complexity
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.
This nested loop approach iterates over every possible subarray, calculating their sums, and counts those with an odd sum.
Complexity
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).
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 | — |
Detailed 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 |
Video Solution
Number of Sub-arrays With Odd Sum - Leetcode 1524 - Python • NeetCodeIO • 15,445 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Number of Sub-arrays With Odd Sum easy or hard?
Number of Sub-arrays With Odd Sum Python/Java solution
How to solve Number of Sub-arrays With Odd Sum in O(n)?
What is the best approach for Number of Sub-arrays With Odd Sum?
Is Number of Sub-arrays With Odd Sum asked at Google/Amazon/Meta?
What data structure is used in Number of Sub-arrays With Odd Sum?
What is the time complexity of Number of Sub-arrays With Odd Sum?
Ready to solve this problem?
Practice Number of Sub-arrays With Odd Sum with our built-in code editor and test cases.
Practice on FleetCode