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 10^9 + 7.

Examples

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 <= 10^5
  • 1 <= arr[i] <= 100

Solution

We are tasked with finding the number of subarrays of an array where the sum of the elements in the subarray is odd.

Video explanation

Here is the video explaining this method in detail. Please check it out:

Method 1 - Naive

A straightforward way to solve the problem is to generate all possible subarrays, calculate their sums, and check if the sum is odd.

Complexity

  • ⏰ Time complexity: O(n^3). Generating the subarrays takes (O(n^2)), and calculating the sum for each subarray adds an (O(n)). As a result, this approach runs in (O(n^3)) time.
  • 🧺 Space complexity: O(1)

Method 2 - Using prefix sums but still naive

To avoid recalculating sums for every subarray, we can use a prefix sum array. Using prefix sums, the sum of any subarray can be calculated in constant time.

  1. Compute the prefix sum array, where each entry stores the cumulative sum of elements from the start of the array up to the current index.
  2. Use two nested loops:
    • The outer loop determines the ending index of the subarray.
    • The inner loop determines the starting index of the subarray.
  3. Calculate the subarray sum using the prefix sum formula: $\text{subarray sum} = \text{prefix sum}[j] - \text{prefix sum}[i - 1]$
  4. Check if the calculated subarray sum is odd, and increment the count accordingly.

Pseudocode

def count_odd_subarrays(arr: List[int]) -> int:
    prefix_sum = [0] * len(arr)
    prefix_sum[0] = arr[0]
    for i in range(1, len(arr)):
        prefix_sum[i] = prefix_sum[i - 1] + arr[i]
    
    count = 0
    for j in range(len(arr)):
        for i in range(j + 1):
            subarray_sum = prefix_sum[j] - (prefix_sum[i - 1] if i > 0 else 0)
            if subarray_sum % 2 != 0:
                count += 1
    
    return count

Complexity

  • ⏰ Time complexity: O(n^2). Precomputing the prefix sum array takes (O(n)). Using nested loops to calculate odd subarray sums runs in (O(n^2)). Therefore, the total complexity is (O(n^2)).
  • 🧺 Space complexity: O(n) due to storing prefix sum.

Method 3 - Using Prefix Sum with parity check

Instead of iterating over all previous prefix sums for each subarray, we use the parity property of prefix sums:

  • Odd - Even = Odd
  • Even - Odd = Odd

By tracking the count of odd and even prefix sums as we iterate over the array, we can directly determine the number of odd-sum subarrays ending at the current index.

Approach

  1. Use a hashmap or two counters (odd and even) to track the counts of odd prefix sums and even prefix sums seen so far.
  2. Start with even = 1 and odd = 0 because the prefix sum 0 (before processing any elements) is considered an even sum.
  3. Iterate through the array, maintaining a current_sum:
    • If current_sum is odd, then:
      • The number of subarrays ending at this index with an odd sum equals the count of even prefix sums seen so far.
      • Increment odd count by 1.
    • If current_sum is even:
      • The number of subarrays ending at this index with an odd sum equals the count of odd prefix sums seen so far.
      • Increment even count by 1.
  4. Accumulate the results in an ans variable during the traversal.

Reasoning

  • For every element processed in the array, updating the odd and even counters helps us keep track of how many odd and even prefix sums there are up to that point in constant time.
  • Using modulo arithmetic ensures the result stays within constraints.

Code

Java
class Solution {
    public int numOfSubarrays(int[] arr) {
        int odd = 0, even = 1; // Start with 1 even prefix sum
        int ans = 0, currSum = 0, mod = 1_000_000_007;

        for (int num : arr) {
            currSum += num;
            if (currSum % 2 == 0) {
                ans += odd;
                even++;
            } else {
                ans += even;
                odd++;
            }
            ans %= mod; // Keep result within bounds of modulo
        }

        return ans;
    }
}
Python
class Solution:
    def numOfSubarrays(self, arr: List[int]) -> int:
        odd, even = 0, 1  # Start with 1 even prefix sum
        ans, curr_sum, mod = 0, 0, 10**9 + 7
        
        for num in arr:
            curr_sum += num
            if curr_sum % 2 == 0:
                ans += odd
                even += 1
            else:
                ans += even
                odd += 1
            
            ans %= mod  # Keep result within bounds of modulo
        
        return ans

Complexity

  • ⏰ Time complexity: O(n) where n is the number of elements in the array because we iterate over the array once.
  • 🧺 Space complexity: O(1) as we only use a few variables for tracking counts and sums.

Dry Run

Suppose arr = [1, 3, 5]:

  • Start with odd = 0, even = 1, ans = 0.
  • Step 1: Add 1 (current_sum = 1 → odd):
    • ans += even → ans = 1.
    • odd++ → odd = 1.
  • Step 2: Add 3 (current_sum = 4 → even):
    • ans += odd → ans = 2.
    • even++ → even = 2.
  • Step 3: Add 5 (current_sum = 9 → odd):
    • ans += even → ans = 4.
    • odd++ → odd = 2.
  • Result: ans = 4.