1524. Number of Sub-arrays With Odd Sum - Detailed Explanation

Problem Statement

You are given an integer array arr. A subarray is a contiguous non-empty sequence of elements within the array. The task is to return the number of subarrays that have an odd sum. Since the answer may be very large, return it modulo (10^9 + 7).

Example 1

• Input: arr = [1, 3, 5]
• Output: 4
• Explanation:
  The subarrays with odd sum are:
  • [1] → sum = 1 (odd)
  • [1, 3, 5] → sum = 9 (odd)
  • [3] → sum = 3 (odd)
  • [5] → sum = 5 (odd)

Example 2

• Input: arr = [2, 4, 6]
• Output: 0
• Explanation:
  All subarrays have an even sum, so there are no subarrays with an odd sum.

Example 3

• Input: arr = [1, 2, 3, 4, 5, 6, 7]
• Output: [Depends on calculation]
  (The answer is determined by counting all subarrays with an odd sum modulo (10^9 + 7).)

Constraints

• (1 \leq \text{arr.length} \leq 10^5)

• (1 \leq \text{arr}[i] \leq 10^5)

Hints to Guide Your Approach

1. Subarray Sum Parity:
   Remember that a subarray sum is odd if and only if the parities (even/odd nature) of its prefix sums differ. In other words, if you know the prefix sum (cumulative sum) up to two indices, the difference (which gives the subarray sum) is odd when one prefix is even and the other is odd.

2. Prefix Sum Modulo 2:
   Instead of keeping track of the full prefix sum, you can simply record whether the prefix sum is even or odd (i.e. compute the prefix sum modulo 2). This reduces the problem to counting how many prefix sums are even and how many are odd.

3. Counting Technique:
   If you know the count of even prefix sums and the count of odd prefix sums, then the number of subarrays with an odd sum is given by multiplying the number of even prefixes by the number of odd prefixes. (This works because a subarray from index (i) to (j) has an odd sum if the parity at (i) is different from the parity at (j+1).)

Approaches to Solve the Problem

Approach: Prefix Sum Parity Counting (Optimal)

Explanation

• Idea:
  As you iterate through the array, maintain a running prefix sum modulo 2. Use two counters:

  • count_even to count the number of prefix sums that are even.
  • count_odd to count the number of prefix sums that are odd.

  Initialize count_even = 1 (since an empty prefix sum is 0, which is even) and count_odd = 0.

• How It Works:
  For each element in the array, update the prefix sum modulo 2:

  • If the updated prefix sum is even, then any previous prefix that was odd will form a subarray with an odd sum with the current position.
  • Similarly, if the prefix sum is odd, then every even prefix before it will form a subarray with an odd sum.

  Therefore, if the current prefix is even, add count_odd to your result; if odd, add count_even to your result. Then update the corresponding counter.

• Modulo Operation:
  Since the answer can be very large, take the result modulo (10^9 + 7) at each step.

Complexity Analysis

• Time Complexity: (O(n)) — we iterate through the array once.

• Space Complexity: (O(1)) — only a few counters and the running prefix sum are used.

Code Implementations

Python Code

Below is the Python implementation using the prefix sum parity counting approach.