LeetCode 1524 - Number of Sub-arrays With Odd Sum

LeetCode Problem 1524

Difficulty: 🟡 Medium
Topics: Array, Math, Dynamic Programming, Prefix Sum

Solution

Problem Understanding

The problem asks us to count the number of subarrays within a given integer array arr whose sums are odd. A subarray is defined as a contiguous segment of the original array. The input is a list of integers, and we need to return the count of subarrays whose total sum is odd. The result must be returned modulo 10^9 + 7 because the count can grow very large.

The constraints tell us that the array can be up to 10^5 elements, and each element ranges from 1 to 100. This indicates that a naive solution that checks every possible subarray will be too slow, as the number of subarrays is O(n^2), which can be up to 10^10 in the worst case.

Important edge cases include arrays where all numbers are even (no odd sum subarrays), all numbers are odd, arrays with a single element, or arrays that have alternating even and odd numbers. The problem guarantees that the array is non-empty, so we do not have to handle an empty input.

Approaches

The brute-force approach involves generating all possible subarrays, computing their sums, and checking whether each sum is odd. While this approach is straightforward and guaranteed to be correct, it is extremely inefficient due to its O(n^2) subarray enumeration and O(n) sum computation per subarray, resulting in O(n^3) time complexity for large arrays.

The optimal approach relies on the key insight that we do not need to calculate each subarray sum individually. Instead, we can use prefix sums and parity tracking. The parity of a subarray sum depends only on the parity of the prefix sums at its endpoints. Specifically, if a prefix sum is odd and we subtract a prefix sum that is even, the resulting subarray sum is odd. Therefore, by tracking the number of prefix sums that are odd and even as we iterate, we can incrementally count the number of subarrays with an odd sum in O(n) time.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n^3)	O(1)	Generate all subarrays, sum them, check odd
Optimal	O(n)	O(1)	Track odd/even prefix sums and update counts dynamically

Algorithm Walkthrough

1. Initialize three variables: odd_count = 0, even_count = 1, and total_odd_subarrays = 0. Here, even_count starts at 1 to account for the "empty prefix sum" which is even.
2. Initialize a running variable current_sum = 0 to keep track of the prefix sum as we iterate through the array.
3. Iterate through each element in arr. For each element, add it to current_sum.
4. Check the parity of current_sum:

• If current_sum is odd, it can form an odd sum with all previous even prefix sums, so increment total_odd_subarrays by even_count. Also increment odd_count by 1 to record this new odd prefix sum.
• If current_sum is even, it can form an odd sum with all previous odd prefix sums, so increment total_odd_subarrays by odd_count. Increment even_count by 1 to record this new even prefix sum.

5. Take the modulo 10^9 + 7 after each increment to avoid overflow.
6. After processing all elements, return total_odd_subarrays.

Why it works: The key invariant is that the parity of a subarray sum from index i to j is equal to the parity difference between prefix_sum[j] and prefix_sum[i-1]. By counting how many prefix sums are even and odd, we can determine in constant time how many subarrays ending at the current index have an odd sum.

Python Solution

from typing import List

class Solution:
    def numOfSubarrays(self, arr: List[int]) -> int:
        MOD = 10**9 + 7
        odd_count = 0
        even_count = 1  # account for the empty prefix sum
        total_odd_subarrays = 0
        current_sum = 0

        for num in arr:
            current_sum += num
            if current_sum % 2 == 0:
                total_odd_subarrays = (total_odd_subarrays + odd_count) % MOD
                even_count += 1
            else:
                total_odd_subarrays = (total_odd_subarrays + even_count) % MOD
                odd_count += 1

        return total_odd_subarrays

The Python implementation follows the algorithm exactly. The current_sum tracks the running prefix sum. Based on whether it is odd or even, we update the total number of odd subarrays using previously counted prefix sums of opposite parity. We use modulo arithmetic to handle large results.

Go Solution

func numOfSubarrays(arr []int) int {
    const MOD = 1_000_000_007
    oddCount, evenCount := 0, 1
    totalOddSubarrays, currentSum := 0, 0

    for _, num := range arr {
        currentSum += num
        if currentSum % 2 == 0 {
            totalOddSubarrays = (totalOddSubarrays + oddCount) % MOD
            evenCount++
        } else {
            totalOddSubarrays = (totalOddSubarrays + evenCount) % MOD
            oddCount++
        }
    }

    return totalOddSubarrays
}

The Go implementation mirrors the Python version, but uses explicit type declarations and const for the modulus. Slices are iterated with range. Overflow is prevented by taking modulo after each update.

Worked Examples

Example 1: arr = [1,3,5]

Step	Current Element	Prefix Sum	Odd Count	Even Count	Total Odd Subarrays
1	1	1	1	1	1
2	3	4	1	2	2
3	5	9	2	2	4

Example 2: arr = [2,4,6]

Step	Current Element	Prefix Sum	Odd Count	Even Count	Total Odd Subarrays
1	2	2	0	2	0
2	4	6	0	3	0
3	6	12	0	4	0

Example 3: arr = [1,2,3,4,5,6,7]

Trace follows same logic; totalOddSubarrays incrementally reaches 16.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Single pass through array of length n
Space	O(1)	Only a few counters are used

This is efficient for large arrays up to 10^5 elements, as it avoids generating subarrays.

Test Cases

# Provided examples
assert Solution().numOfSubarrays([1,3,5]) == 4  # mixed odd numbers
assert Solution().numOfSubarrays([2,4,6]) == 0  # all even numbers
assert Solution().numOfSubarrays([1,2,3,4,5,6,7]) == 16  # mixed sequence

# Edge cases
assert Solution().numOfSubarrays([1]) == 1  # single odd element
assert Solution().numOfSubarrays([2]) == 0  # single even element
assert Solution().numOfSubarrays([1,1,1,1]) == 6  # all odd elements
assert Solution().numOfSubarrays([2,2,2,2]) == 0  # all even elements
assert Solution().numOfSubarrays([1,2,1,2,1]) == 9  # alternating odd and even

Test	Why
[1,3,5]	Basic case with all odd numbers
[2,4,6]	No odd sums, all even
[1,2,3,4,5,6,7]	Larger array with mixed numbers
[1]	Single element odd
[2]	Single element even
[1,1,1,1]	All odd, multiple overlapping subarrays
[2,2,2,2]	All even, no odd sum subarrays
[1,2,1,2,1]	Alternating parity pattern

Edge Cases

Single-element array: If the array has only one element, the result is either 0 or 1 depending on the parity. The algorithm handles this by correctly initializing even_count and updating total_odd_subarrays.

All even numbers: In this case, current_sum never becomes odd, so total_odd_subarrays remains zero. The algorithm counts correctly because no updates are made from odd_count.

All odd numbers: Every new odd