Watch 10 video solutions for Number of Sub-arrays With Odd Sum, a medium level problem involving Array, Math, Dynamic Programming. This walkthrough by NeetCodeIO has 15,012 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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] <= 100Problem 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 | 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 |