Number of Sub-arrays With Odd Sum
MedPrompt
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
Approaches
3 approaches with complexity analysis and trade-offs.
This is the most straightforward but also the most inefficient approach. It involves generating every possible subarray, calculating the sum of its elements, and checking if the sum is odd. A counter is maintained for subarrays that satisfy the condition.
Algorithm
- Initialize
result = 0andMOD = 1_000_000_007. - Use a nested loop to define the start (
i) and end (j) of each subarray. - For each subarray
arr[i...j], use a third loop to iterate fromitojand calculate its sum. - Check if the sum is odd (
sum % 2 != 0). - If the sum is odd, increment the
resultcounter, applying the modulo operation:result = (result + 1) % MOD. - After checking all subarrays, return
result.
Walkthrough
The brute-force method systematically checks every single contiguous subarray within the given array arr. It uses three nested loops to achieve this:
- The first loop, with index
i, iterates from the beginning to the end of the array to select the starting element of a subarray. - The second loop, with index
j, iterates fromito the end of the array to select the ending element of the subarray. - The third loop, with index
k, iterates fromitojto compute the sum of the elements in the current subarrayarr[i...j].
After calculating the sum, we check if it's odd. If it is, we increment a counter. To handle potentially large results, the counter is updated using modulo arithmetic at each increment. While simple to understand, its cubic time complexity makes it impractical for large inputs.
class Solution { public int numOfSubarrays(int[] arr) { int n = arr.length; int result = 0; int MOD = 1_000_000_007; for (int i = 0; i < n; i++) { for (int j = i; j < n; j++) { int currentSum = 0; for (int k = i; k <= j; k++) { currentSum += arr[k]; } if (currentSum % 2 != 0) { result = (result + 1) % MOD; } } } return result; }}Complexity
Time
O(N³), where N is the number of elements in `arr`. The three nested loops lead to a cubic time complexity, which is very slow.
Space
O(1), as we only use a few variables to store indices and the current sum. No extra space proportional to the input size is needed.
Trade-offs
Pros
Very simple to understand and implement.
Requires no special data structures or complex logic.
Cons
Extremely inefficient due to three nested loops.
Will result in a 'Time Limit Exceeded' error for the given constraints.
This approach is an optimization of the pure brute-force method. Instead of recalculating the sum of each subarray from scratch, we use a running sum. We iterate through all possible starting points and, for each, extend the subarray one element at a time, updating the sum and checking its parity.
Algorithm
- Initialize
result = 0andMOD = 1_000_000_007. - Use an outer loop with index
ito fix the starting point of subarrays. - Inside, initialize
currentSum = 0. - Use an inner loop with index
jstarting fromito extend the subarray to the right. - In the inner loop, update the sum:
currentSum += arr[j]. - Check if
currentSumis odd. If so, incrementresultwith modulo:result = (result + 1) % MOD. - After the loops complete, return
result.
Walkthrough
We can eliminate one of the nested loops from the previous approach. We still use two nested loops to define all subarrays.
- The outer loop (with index
i) fixes the starting point of the subarray. - The inner loop (with index
j) iterates fromito the end of the array. This loop defines the ending point and effectively extends the subarray one element at a time.
A variable currentSum is maintained for each starting point i. As the inner loop progresses, currentSum is updated by adding the next element arr[j]. This currentSum represents the sum of the subarray arr[i...j]. After each update, we check if currentSum is odd and update our result counter accordingly. This reduces the complexity from cubic to quadratic.
class Solution { public int numOfSubarrays(int[] arr) { int n = arr.length; int result = 0; int MOD = 1_000_000_007; for (int i = 0; i < n; i++) { int currentSum = 0; for (int j = i; j < n; j++) { currentSum += arr[j]; if (currentSum % 2 != 0) { result = (result + 1) % MOD; } } } return result; }}Complexity
Time
O(N²), where N is the length of the array. The two nested loops result in quadratic time complexity.
Space
O(1), as we only use a constant amount of extra space for variables.
Trade-offs
Pros
Significantly faster than the O(N³) approach.
Remains relatively simple to implement.
Cons
Still inefficient for large inputs.
Guaranteed to time out on competitive programming platforms for constraints like N = 10^5.
This is the most efficient approach, solving the problem in a single pass. It relies on the mathematical property of sums and parity. The sum of a subarray arr[i...j] is odd if and only if the parity of the prefix sum up to j is different from the parity of the prefix sum up to i-1. By keeping track of the counts of even and odd prefix sums seen so far, we can calculate the result in linear time.
Algorithm
- Initialize
odd = 0(count of odd-parity prefix sums),even = 1(for the initial even-parity prefix sum of 0),result = 0, andcurrentParity = 0. - Define
MOD = 1_000_000_007. - Iterate through each number
numinarr. - Update the parity of the running sum:
currentParity = (currentParity + num) % 2. - If
currentParityis 1 (odd):- The number of new odd-sum subarrays ending here is
even. - Update
result = (result + even) % MOD. - Increment
odd.
- The number of new odd-sum subarrays ending here is
- If
currentParityis 0 (even):- The number of new odd-sum subarrays ending here is
odd. - Update
result = (result + odd) % MOD. - Increment
even.
- The number of new odd-sum subarrays ending here is
- Return
result.
Walkthrough
The key insight is that sum(arr[i..j]) = prefixSum[j] - prefixSum[i-1]. For this sum to be odd, the parities must differ:
odd_sum = odd_prefix - even_prefixodd_sum = even_prefix - odd_prefix
We can iterate through the array once, maintaining a running sum's parity. We also keep two counters: oddCount for the number of prefix sums with odd parity encountered so far, and evenCount for those with even parity. We initialize evenCount = 1 to account for the empty prefix sum (sum=0, which is even).
For each element arr[i], we update the current prefix sum's parity.
- If the new prefix sum is odd, it can be paired with any of the
evenCountpreviously seen even prefix sums to form a subarray with an odd sum. We addevenCountto our result and then incrementoddCount. - If the new prefix sum is even, it can be paired with any of the
oddCountpreviously seen odd prefix sums. We addoddCountto our result and then incrementevenCount.
This method avoids nested loops entirely, leading to an optimal solution.
class Solution { public int numOfSubarrays(int[] arr) { int MOD = 1_000_000_007; int oddCount = 0; // count of prefix sums with odd parity int evenCount = 1; // count of prefix sums with even parity (starts with 1 for empty prefix sum 0) int result = 0; int currentSumParity = 0; // 0 for even, 1 for odd for (int num : arr) { currentSumParity = (currentSumParity + num) % 2; if (currentSumParity == 1) { // current prefix sum is odd // Pair with previous even prefix sums result = (result + evenCount) % MOD; oddCount++; } else { // current prefix sum is even // Pair with previous odd prefix sums result = (result + oddCount) % MOD; evenCount++; } } return result; }}Complexity
Time
O(N), where N is the length of the array. We iterate through the array only once.
Space
O(1), as it only requires a few variables to store the counts and current parity, regardless of the input size.
Trade-offs
Pros
Optimal time complexity, making it very fast.
Optimal space complexity.
Passes for all constraints.
Cons
The logic is less direct and might require some thought to understand compared to brute-force methods.
Solutions
Solution
class Solution {public int numOfSubarrays(int[] arr) { final int mod = (int)1 e9 + 7; int[] cnt = {1, 0}; int ans = 0, s = 0; for (int x : arr) { s += x; ans = (ans + cnt[s & 1 ^ 1]) % mod; ++cnt[s & 1]; } return ans; }}class Solution { public: int numOfSubarrays ( vector < int >& arr ) { const int mod = 1e9 + 7 ; int cnt [ 2 ] = { 1 , 0 }; int ans = 0 , s = 0 ; for ( int x : arr ) { s += x ; ans = ( ans + cnt [ s & 1 ^ 1 ]) % mod ; ++ cnt [ s & 1 ]; } return ans ; } };class Solution: def numOfSubarrays(self, arr: List[int]) -> int: mod = 10 ** 9 + 7 cnt = [1, 0] ans = s = 0 for x in arr: s += x ans = (ans + cnt[s & 1 ^ 1]) % mod cnt[s & 1] += 1 return ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.