Domain 2MediumMEDIUM

Number of Sub-arrays With Odd Sum

LeetCode problem 1524: Number of Sub-arrays With Odd Sum (medium).

Domain: medium•Updated: 2026-09-17
#Array#Math

Problem Breakdown

We are given an array of integers arr. The goal is to count how many contiguous sub-arrays have a sum that is odd. We must return the result modulo 109+710^9 + 7.

Inputs: An integer list arr where length ranges from 1 to 10510^5 and values are between 1 and 100 (though parity logic holds regardless of value range). Outputs: A single non-negative integer representing the count. Implicit Constraints & Edge Cases:

  • Modulo Arithmetic: The result can exceed standard integer limits in languages like C++/Java, so we must apply modulo 109+710^9 + 7. Python handles large integers automatically, but applying the modulus at return is required by problem spec.
  • Sub-array Definition: Any slice arr[i:j] inclusive of start and exclusive of end (standard definition).
  • Initial State: The sum before any elements are processed is effectively 0 (even), which acts as a virtual prefix for sub-arrays starting at index 0.

Intuition

A naive approach would iterate through every possible pair (i, j) representing start and end indices of a sub-array, calculate the sum using slicing or accumulation, check parity, and increment a counter.

  • Brute Force Complexity: O(N2)O(N^2) because there are roughly N2/2N^2/2 sub-arrays. Given N=105N=10^5, this will Time Out (TLE).

Key Insight: Prefix Sums & Parity Properties. The sum of a sub-array arr[i..j] can be expressed as the difference between two prefix sums: Prefix[j+1] - Prefix[i-1]. In modular arithmetic modulo 2 (parity):

  • (Odd + Even) % 2 = Odd
  • (Even + Even) % 2 = Even
  • (Odd + Odd) % 2 = Even

Essentially, a sub-array sum is odd if and only if the two prefix sums defining it have different parities. One must be even and one odd. If we know how many times an “even” prefix sum has occurred previously in our scan, and we encounter an “odd” current prefix sum now, every previous occurrence of that specific parity forms a valid sub-array with us right here.

Approach

  1. Initialize total_odd_subarrays = 0.
  2. Maintain counters for how many times we have seen:
    • An even running prefix sum so far (count_even).
    • An odd running prefix sum so far (count_odd).
  3. Start with a virtual prefix sum of 0 (which is even). So, initialize count_even = 1, count_odd = 0.
  4. Iterate through each number in the array:
    • Update the current running sum parity by adding the current element modulo 2.
    • If the new prefix sum is odd: It can form an odd sub-array with any previous even prefix sums found so far. Add count_even to our total answer, then increment count_odd.
    • If the new prefix sum is even: It can form an odd sub-array with any previous odd prefix sums found so far. Add count_odd to our total answer, then increment count_even.
  5. Return the accumulated count modulo 109+710^9 + 7.

Complexity Analysis

  • Time Complexity: O(N)O(N) where NN is the length of arr. We iterate through the array exactly once performing constant-time operations per element.
  • Space Complexity: O(1)O(1). We only store a few integer counters regardless of input size (excluding Python’s internal large int storage overhead).

Solution

class Solution:
    def numOfSubarrays(self, arr: List[int]) -> int:
        MOD = 10**9 + 7
        
        # Counters for prefix sums parity. 
        # Initial sum is 0 (even), so we start with one even count.
        odd_count = 0
        even_count = 1 
        
        current_sum_parity = 0
        total_odd_subarrays = 0
        
        for num in arr:
            # Update running parity based on the number's parity 
            # (num % 2) is sufficient to track sum parity without full value.
            if num % 2 == 1:
                current_sum_parity ^= 1
            
            # If current prefix is odd, it pairs with all previous even prefixes
            if current_sum_parity == 1:
                total_odd_subarrays = (total_odd_subarrays + even_count) % MOD
                odd_count += 1
            else:
                # If current prefix is even, it pairs with all previous odd prefixes
                total_odd_subarrays = (total_odd_subarrays + odd_count) % MOD
                even_count += 1
                
        return total_odd_subarrays

Edge Cases Handled

  • Single Element Array: The loop runs once. If the element is odd, even_count (initially 1) pairs with it to make a sub-array sum of that single element. Correct.
  • All Even Numbers: current_sum_parity remains even throughout. We only add odd_count which stays at 0. Result is 0. Correct.
  • Large Output Count: The modulo operation ensures the result fits within standard integer limits for languages like Java/C++, and adheres to problem requirements in Python as well.