Facebook Pixel

1524. Number of Sub-arrays With Odd Sum

MediumArrayMathDynamic ProgrammingPrefix Sum
Leetcode Link

Problem Description

You are given an array of integers arr. Your task is to find the total number of subarrays that have an odd sum.

A subarray is a contiguous sequence of elements from the array. For example, if arr = [1, 2, 3], then the subarrays are [1], [2], [3], [1, 2], [2, 3], and [1, 2, 3].

You need to count how many of these subarrays have a sum that is an odd number.

Since the answer can be very large, return the result modulo 10^9 + 7.

For example:

  • If arr = [1, 3, 5], the subarrays with odd sums are [1], [3], [5], and [1, 3, 5], giving us 4 subarrays with odd sums.
  • A subarray like [1, 3] has sum 4 (even), so it wouldn't be counted.

The key insight is that a subarray has an odd sum if and only if it contains an odd number of odd elements. The solution uses prefix sums and tracks the parity (even/odd) of cumulative sums to efficiently count all subarrays with odd sums.

Quick Interview Experience
Help others by sharing your interview experience
Have you seen this problem before?

Intuition

To understand how to count subarrays with odd sums efficiently, let's think about when a subarray has an odd sum.

First, recall that:

  • odd + odd = even
  • even + even = even
  • odd + even = odd

For any subarray from index i to j, we can express its sum using prefix sums: sum[i...j] = prefixSum[j] - prefixSum[i-1].

Now here's the key insight: The subarray sum is odd when prefixSum[j] - prefixSum[i-1] is odd. This happens when one prefix sum is even and the other is odd (since odd - even = odd, and even - odd = odd).

So as we traverse the array and calculate the running prefix sum at each position:

  • If the current prefix sum is even, all previous odd prefix sums will create subarrays with odd sums ending at the current position
  • If the current prefix sum is odd, all previous even prefix sums will create subarrays with odd sums ending at the current position

This means we need to track two things:

  1. The count of even prefix sums we've seen so far
  2. The count of odd prefix sums we've seen so far

At each position, we check the parity of our current prefix sum, then add the count of opposite parity prefix sums to our answer. This gives us all subarrays with odd sums ending at the current position.

We start with cnt[0] = 1 (representing the empty prefix with sum 0, which is even) and cnt[1] = 0. The bit operation s & 1 gives us the parity (0 for even, 1 for odd), and s & 1 ^ 1 gives us the opposite parity.

Learn more about Math, Dynamic Programming and Prefix Sum patterns.

Solution Approach

We implement the solution using a prefix sum approach combined with a parity counter.

Data Structures:

  • cnt: An array of size 2 where cnt[0] tracks the count of even prefix sums and cnt[1] tracks the count of odd prefix sums. Initialize with cnt = [1, 0] since we start with a prefix sum of 0 (which is even).
  • s: Running prefix sum, initialized to 0
  • ans: Counter for the final answer
  • mod: The modulo value 10^9 + 7

Algorithm Steps:

  1. Initialize the counter: Set cnt = [1, 0] because before processing any elements, we have one prefix sum of value 0 (which is even).

  2. Traverse the array: For each element x in arr:

    • Update prefix sum: Add x to the running sum s
    • Count valid subarrays:
      • Calculate s & 1 to get the parity of current prefix sum (0 if even, 1 if odd)
      • Calculate s & 1 ^ 1 to get the opposite parity
      • Add cnt[s & 1 ^ 1] to the answer - this counts all subarrays ending at current position with odd sum
    • Update counter: Increment cnt[s & 1] by 1 to record this prefix sum's parity

  3. Apply modulo: Since the answer can be large, apply modulo 10^9 + 7 when updating the answer.

Why this works:

  • When current prefix sum is even (s & 1 = 0), we need previous odd prefix sums (cnt[1]) to create odd-sum subarrays
  • When current prefix sum is odd (s & 1 = 1), we need previous even prefix sums (cnt[0]) to create odd-sum subarrays
  • The XOR operation s & 1 ^ 1 efficiently flips the parity bit to get the opposite parity

Time Complexity: O(n) where n is the length of the array, as we make a single pass through the array.

Space Complexity: O(1) as we only use a fixed amount of extra space regardless of input size.

Ready to land your dream job?

Unlock your dream job with a 5-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through the solution with arr = [1, 2, 3].

Initial Setup:

  • cnt = [1, 0] (one even prefix sum of 0)
  • s = 0 (running prefix sum)
  • ans = 0 (count of odd-sum subarrays)

Step 1: Process element 1

  • Update prefix sum: s = 0 + 1 = 1
  • Current parity: s & 1 = 1 (odd)
  • Opposite parity: s & 1 ^ 1 = 0 (even)
  • Add subarrays with odd sum: ans += cnt[0] = 1
    • This counts subarray [1] (from index 0 to 0)
  • Update counter: cnt[1]++ → cnt = [1, 1]

Step 2: Process element 2

  • Update prefix sum: s = 1 + 2 = 3
  • Current parity: s & 1 = 1 (odd)
  • Opposite parity: s & 1 ^ 1 = 0 (even)
  • Add subarrays with odd sum: ans += cnt[0] = 1, so ans = 2
    • This counts subarray [1,2,3] (prefix sum 3 - prefix sum 0)
  • Update counter: cnt[1]++ → cnt = [1, 2]

Step 3: Process element 3

  • Update prefix sum: s = 3 + 3 = 6
  • Current parity: s & 1 = 0 (even)
  • Opposite parity: s & 1 ^ 1 = 1 (odd)
  • Add subarrays with odd sum: ans += cnt[1] = 2, so ans = 4
    • This counts subarrays [3] (prefix sum 6 - prefix sum 3) and [2,3] (prefix sum 6 - prefix sum 1)
  • Update counter: cnt[0]++ → cnt = [2, 2]

Final Answer: 4

The subarrays with odd sums are:

  1. [1] - sum = 1 (odd)
  2. [1,2,3] - sum = 6 (identified as 3-0, but we need odd difference)
  3. [3] - sum = 3 (odd)
  4. [2,3] - sum = 5 (odd)

Actually, let me recalculate step 2:

  • At step 2, prefix sum = 3 (odd), we look for even prefix sums
  • We have prefix sum 0 (even), so subarray from after position -1 to position 1 gives us [1,2] with sum 3 (odd)

The four odd-sum subarrays are: [1], [1,2], [3], and [2,3].

Solution Implementation

1class Solution:
2    def numOfSubarrays(self, arr: List[int]) -> int:
3        MOD = 10**9 + 7
4      
5        # Count of prefix sums by parity: [even_count, odd_count]
6        # Initialize with [1, 0] since empty prefix has sum 0 (even)
7        parity_count = [1, 0]
8      
9        # Total count of subarrays with odd sum
10        result = 0
11      
12        # Running prefix sum
13        prefix_sum = 0
14      
15        for num in arr:
16            # Update prefix sum
17            prefix_sum += num
18          
19            # Get current parity (0 for even, 1 for odd)
20            current_parity = prefix_sum & 1
21          
22            # To get odd sum subarray, we need opposite parity
23            # If current is even (0), we need odd (1): 0 ^ 1 = 1
24            # If current is odd (1), we need even (0): 1 ^ 1 = 0
25            opposite_parity = current_parity ^ 1
26          
27            # Add count of prefix sums with opposite parity
28            result = (result + parity_count[opposite_parity]) % MOD
29          
30            # Update count for current parity
31            parity_count[current_parity] += 1
32      
33        return result
34
1class Solution {
2    public int numOfSubarrays(int[] arr) {
3        final int MOD = 1_000_000_007;
4      
5        // Count of prefix sums by parity: [even count, odd count]
6        // Initially, we have one prefix with sum 0 (even)
7        int[] prefixCountByParity = {1, 0};
8      
9        int result = 0;
10        int prefixSum = 0;
11      
12        for (int num : arr) {
13            // Update the running prefix sum
14            prefixSum += num;
15          
16            // Determine current prefix sum parity (0 for even, 1 for odd)
17            int currentParity = prefixSum & 1;
18          
19            // To get odd subarray sum ending at current position:
20            // - If current prefix is odd, we need even prefix before
21            // - If current prefix is even, we need odd prefix before
22            // XOR with 1 flips the parity (0^1=1, 1^1=0)
23            int requiredParity = currentParity ^ 1;
24          
25            // Add count of prefixes with required parity to result
26            result = (result + prefixCountByParity[requiredParity]) % MOD;
27          
28            // Increment count for current prefix sum parity
29            prefixCountByParity[currentParity]++;
30        }
31      
32        return result;
33    }
34}
35
1class Solution {
2public:
3    int numOfSubarrays(vector<int>& arr) {
4        const int MOD = 1e9 + 7;
5      
6        // count[0]: count of even prefix sums
7        // count[1]: count of odd prefix sums
8        // Initialize with count[0] = 1 for empty prefix (sum = 0, which is even)
9        int count[2] = {1, 0};
10      
11        int result = 0;
12        int prefixSum = 0;
13      
14        for (int num : arr) {
15            // Update the running prefix sum
16            prefixSum += num;
17          
18            // If current prefix sum is odd, we need previous even prefix sums
19            // If current prefix sum is even, we need previous odd prefix sums
20            // This is achieved by XOR with 1: (prefixSum & 1) ^ 1
21            int parityNeeded = (prefixSum & 1) ^ 1;
22            result = (result + count[parityNeeded]) % MOD;
23          
24            // Increment count for current prefix sum parity
25            int currentParity = prefixSum & 1;
26            ++count[currentParity];
27        }
28      
29        return result;
30    }
31};
32
1/**
2 * Counts the number of subarrays with odd sum
3 * @param arr - The input array of numbers
4 * @returns The count of subarrays with odd sum, modulo 10^9 + 7
5 */
6function numOfSubarrays(arr: number[]): number {
7    let result: number = 0;
8    let prefixSum: number = 0;
9  
10    // Track count of even and odd prefix sums
11    // evenOddCount[0] = count of even prefix sums
12    // evenOddCount[1] = count of odd prefix sums
13    // Initialize with [1, 0] since empty prefix has sum 0 (even)
14    const evenOddCount: number[] = [1, 0];
15  
16    const MOD: number = 1e9 + 7;
17  
18    for (const num of arr) {
19        // Update the running prefix sum
20        prefixSum += num;
21      
22        // Get the parity of current prefix sum (0 for even, 1 for odd)
23        const currentParity: number = prefixSum & 1;
24      
25        // To get odd sum subarray, we need:
26        // - If current prefix sum is odd, pair with even prefix sums
27        // - If current prefix sum is even, pair with odd prefix sums
28        // XOR with 1 flips the parity (0^1=1, 1^1=0)
29        const oppositeParity: number = currentParity ^ 1;
30      
31        // Add count of prefix sums with opposite parity
32        result = (result + evenOddCount[oppositeParity]) % MOD;
33      
34        // Increment count for current prefix sum parity
35        evenOddCount[currentParity]++;
36    }
37  
38    return result;
39}
40

Time and Space Complexity

Time Complexity: O(n) where n is the length of the input array arr. The algorithm iterates through the array exactly once, performing constant-time operations for each element (addition, modulo operation, bitwise operations, and array access/update).

Space Complexity: O(1). The algorithm uses only a fixed amount of extra space regardless of the input size. The variables used are:

  • mod: a constant integer
  • cnt: an array of fixed size 2
  • ans: an integer to store the result
  • s: an integer to track the running sum
  • x: a temporary variable for iteration

All these variables occupy constant space that doesn't scale with the input size.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Forgetting to Initialize the Parity Counter Correctly

The Pitfall: A common mistake is initializing parity_count = [0, 0] instead of [1, 0]. This misses the fact that before processing any elements, we have an implicit prefix sum of 0 (which is even).

Why It Matters:

  • When we encounter the first element, we need to consider subarrays that start from index 0
  • If the first element is odd, the subarray [arr[0]] has an odd sum
  • This requires comparing against a "previous" even prefix sum (the implicit 0)
  • Without parity_count = [1, 0], we'd miss counting these subarrays that start at the beginning

Example of the Bug:

# INCORRECT initialization
parity_count = [0, 0]  # This will miss subarrays starting at index 0

For arr = [1, 2, 3]:

  • With wrong initialization: Would miss counting [1] as an odd-sum subarray
  • With correct initialization: Properly counts all subarrays including those starting at index 0

The Fix:

# CORRECT initialization
parity_count = [1, 0]  # Accounts for the implicit prefix sum of 0

2. Incorrect Parity Calculation Using Modulo Instead of Bitwise AND

The Pitfall: Using prefix_sum % 2 instead of prefix_sum & 1 for parity checking. While both give correct results, there's a subtle issue with negative numbers in some languages.

Why It Matters:

  • In Python, this isn't typically an issue, but it's good practice to use bitwise operations
  • prefix_sum & 1 is more efficient and universally correct
  • In languages like Java or C++, (-3) % 2 might return -1 instead of 1, causing array index errors

Example of the Bug:

# Potentially problematic in other languages
current_parity = prefix_sum % 2  # Could be negative in some languages

The Fix:

# Always safe and efficient
current_parity = prefix_sum & 1  # Always returns 0 or 1

3. Forgetting to Apply Modulo During Accumulation

The Pitfall: Applying modulo only at the end instead of during each addition can cause integer overflow in languages with fixed integer sizes.

Example of the Bug:

# INCORRECT - might overflow in other languages
for num in arr:
    prefix_sum += num
    current_parity = prefix_sum & 1
    opposite_parity = current_parity ^ 1
    result += parity_count[opposite_parity]  # No modulo here
    parity_count[current_parity] += 1

return result % MOD  # Only applying modulo at the end

The Fix:

# CORRECT - apply modulo during accumulation
result = (result + parity_count[opposite_parity]) % MOD

This ensures the result never exceeds the bounds even in languages with fixed-size integers.

Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Tailor Your Study Plan:

Given a sorted array of integers and an integer called target, find the element that equals to the target and return its index. Select the correct code that fills the ___ in the given code snippet.

1def binary_search(arr, target):
2    left, right = 0, len(arr) - 1
3    while left ___ right:
4        mid = (left + right) // 2
5        if arr[mid] == target:
6            return mid
7        if arr[mid] < target:
8            ___ = mid + 1
9        else:
10            ___ = mid - 1
11    return -1
12
1public static int binarySearch(int[] arr, int target) {
2    int left = 0;
3    int right = arr.length - 1;
4
5    while (left ___ right) {
6        int mid = left + (right - left) / 2;
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16
1function binarySearch(arr, target) {
2    let left = 0;
3    let right = arr.length - 1;
4
5    while (left ___ right) {
6        let mid = left + Math.trunc((right - left) / 2);
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16

Recommended Readings

Math Basics

Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you

Dynamic Programming Introduction and Patterns

What is Dynamic Programming Prerequisite DFS problems dfs_intro Backtracking problems backtracking Memoization problems memoization_intro Pruning problems backtracking_pruning Dynamic programming is an algorithmic optimization technique that breaks down a complicated problem into smaller overlapping sub problems in a recursive manner and uses solutions to the sub problems to construct a solution

Prefix Sum

Prefix Sum The prefix sum is an incredibly powerful and straightforward technique Its primary goal is to allow for constant time range sum queries on an array What is Prefix Sum The prefix sum of an array at index i is the sum of all numbers from index 0 to i By

Want a Structured Path to Master System Design Too? Don’t Miss This!

Load More