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.
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; }}Video 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.