Number of Sub-arrays With Odd Sum: Prefix Sum Parity

May 31, 20266 min read

leetcodeproblemmediumarraysmathdynamic-programming

LeetCode 1524, Number of Sub-arrays With Odd Sum, is a counting problem that looks like it needs nested loops until you notice a clean mathematical shortcut. The trick is to track whether each prefix sum is even or odd. Two counters replace the entire brute force, and you get an O(n) solution with O(1) space.

The 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.

arr = [1, 3, 5]  -> 4
arr = [2, 4, 6]  -> 0
arr = [1, 2, 3, 4, 5, 6, 7]  -> 16

A subarray is a contiguous, non-empty slice of the array. You need to count every subarray whose elements add up to an odd number.

arr = [1, 3, 5]. Prefix sums [0, 1, 4, 9] have parities [even, odd, even, odd]. Every pair where one is even and the other is odd produces a subarray with an odd sum. Here: 2 even times 2 odd = 4 odd-sum subarrays.

The brute force approach

The most direct way is to enumerate all subarrays, compute each sum, and check if it is odd. For every starting index i you iterate through every ending index j, maintain a running sum, and increment the count when the sum is odd.

def numOfSubarrays(arr):
    MOD = 10 ** 9 + 7
    count = 0
    for i in range(len(arr)):
        total = 0
        for j in range(i, len(arr)):
            total += arr[j]
            if total % 2 == 1:
                count += 1
    return count % MOD

This works correctly but runs in O(n^2) time. For an array of length 100,000, that is 10 billion operations. You need something faster.

The key insight

Think about what makes a subarray sum odd. The sum of arr[i..j] equals prefix[j+1] - prefix[i], where prefix[k] is the sum of the first k elements. A difference of two numbers is odd only when one number is even and the other is odd. So:

If prefix[j+1] is odd and prefix[i] is even, the subarray sum is odd.
If prefix[j+1] is even and prefix[i] is odd, the subarray sum is odd.
If both have the same parity, the difference is even.

You do not need to store every prefix sum value. You only need to know how many previous prefix sums were even and how many were odd. When the current prefix sum is odd, it pairs with every previous even prefix sum. When the current prefix sum is even, it pairs with every previous odd prefix sum.

You do not need a hash map here. Unlike Subarray Sum Equals K where you track exact prefix sum values, this problem only cares about parity. Two integer counters (one for even, one for odd) are all you need.

Step-by-step walkthrough

Step 0: Initialize counters. even = 1, odd = 0, prefix = 0

result = 0. The initial prefix sum 0 is even, so we start with even = 1. This accounts for subarrays that start from the very beginning.

Step 1: arr[0] = 1. prefix = 1 (odd). result += even = 1.

result = 1. Prefix sum is odd, so it pairs with all 1 previous even prefix sum(s). Subarray [1] has odd sum. Increment odd to 1.

Step 2: arr[1] = 3. prefix = 4 (even). result += odd = 1.

result = 2. Prefix sum is even, so it pairs with all 1 previous odd prefix sum(s). Subarray [3] has odd sum. Increment even to 2.

Step 3: arr[2] = 5. prefix = 9 (odd). result += even = 2.

result = 4. Prefix sum is odd, so it pairs with all 2 previous even prefix sum(s). Subarrays [1,3,5] and [5] have odd sums. Done! Answer is 4.

Practice prefix sum problems

The code

def numOfSubarrays(arr):
    MOD = 10 ** 9 + 7
    even = 1
    odd = 0
    prefix = 0
    result = 0
    for x in arr:
        prefix += x
        if prefix % 2 == 0:
            result += odd
            even += 1
        else:
            result += even
            odd += 1
    return result % MOD

Here is how it works:

Start with even = 1 and odd = 0. The initial prefix sum is 0, which is even. This seed ensures you count subarrays that start from index 0.
Update the running prefix sum. For each element, add it to the running total.
Check the parity of the current prefix sum. If it is even, it pairs with all previous odd prefix sums (because even minus odd is odd). If it is odd, it pairs with all previous even prefix sums (because odd minus even is odd).
Increment the appropriate counter. After checking, record the current prefix sum's parity so future elements can reference it.

The modular reduction % MOD only needs to happen once at the end because you are summing counts (which are always non-negative). The intermediate result value can grow large, but Python handles arbitrary-precision integers natively. In languages like Java or C++, you would apply % MOD inside the loop to prevent overflow.

Complexity analysis

Approach	Time	Space
Brute force	O(n^2)	O(1)
Prefix parity	O(n)	O(1)

Time: O(n). You iterate through the array once. Each iteration does a constant amount of work: one addition, one modulo check, one counter increment, and one addition to the result.

Space: O(1). You only store four integer variables (even, odd, prefix, result) regardless of the input size. No hash map, no auxiliary array.

Drill prefix sum patterns

The building blocks

Prefix sum parity

This problem is a special case of the prefix sum counting pattern. Instead of tracking exact prefix sum values in a hash map, you collapse all prefix sums into two buckets: even and odd. The reason this works is that odd/even subtraction follows a fixed rule (odd minus even is odd, even minus odd is odd, everything else is even). You lose the ability to answer "which subarrays sum to exactly k?" but you gain O(1) space and a simpler algorithm.

Counting pairs with complementary properties

The core operation is: when you see an odd prefix sum, you want to know how many even prefix sums you have seen before. This is the same "count complements" idea that appears in Two Sum (count values equal to target - current) and Subarray Sums Divisible by K (count prefix sums with matching remainder). The difference is that here there are only two "classes" (even and odd), so you need just two counters instead of a hash map.

Edge cases

All even elements. Every prefix sum is even, so odd stays at 0 forever. The result is 0 because no pair of prefix sums has mixed parity. Example: [2, 4, 6] returns 0.
All odd elements. Prefix sums alternate between odd and even. A single odd element gives odd prefix sum, two odd elements give even prefix sum, and so on. The even and odd counters grow roughly equally.
Single element. If arr = [x], there is exactly one subarray. The result is 1 if x is odd, 0 if x is even.
Large values. The problem guarantees array values up to 10^4 and length up to 10^5. The result can be as large as roughly n^2 / 2, which exceeds 10^9 + 7, so the modular reduction at the end is essential.
Mix of odd and even elements. The general case. Each odd element flips the parity of the prefix sum, and each even element preserves it.

From understanding to recall

The prefix sum parity trick is elegant, but the details matter when you are writing it under time pressure. You need to remember that even starts at 1 (not 0) because the initial prefix sum of 0 is even. You need to remember to check parity before incrementing the counter, so you do not count a prefix sum as pairing with itself. And you need to remember which counter to add to result in each case (odd prefix sum pairs with even count, and vice versa).

Spaced repetition locks these details into long-term memory. After a few review sessions spread over days and weeks, you will write this solution from scratch without hesitation and recognize the parity counting pattern when it appears in disguise on other problems.

Build recall with CodeBricks

Subarray Sum Equals K - The classic prefix sum counting pattern with a hash map
Continuous Subarray Sum - Prefix sum with modular arithmetic to check divisibility
Subarray Sums Divisible by K - Prefix sum parity generalized to mod-k remainder counting

Try CodeBricks free