1524. Number of Sub-arrays With Odd Sum Medium

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.

Example 1:
Input: arr = [1,3,5]
Output: 4
Explanation: All subarrays are [[1],[1,3],[1,3,5],[3],[3,5],[5]].
All sub-arrays sum are [1,4,9,3,8,5].
Odd sums are [1,9,3,5] so the answer is 4.

Example 2:
Input: arr = [2,4,6]
Output: 0
Explanation: All subarrays are [[2],[2,4],[2,4,6],[4],[4,6],[6]].
All sub-arrays sum are [2,6,12,4,10,6].
All sub-arrays have even sum and the answer is 0.

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

Example 4:
Input: arr = [100,100,99,99]
Output: 4

Example 5:
Input: arr = [7]
Output: 1

Approach

Input: An integer array arr

Output: Return the number of subarrays with an odd sum

This problem belongs to the 1D Prefix Sum category.

First, we need to know the properties of addition:

• Odd + Odd = Even
• Odd + Even = Odd

So to get a subarray with an odd sum, we can use the prefix sum (preSum) to deduce how many subarrays ending at the current index have an odd sum based on the frequency of previous odd and even prefix sums.

• When preSum is odd, it can only come from Odd = Odd + Even combinations. Hence, the number of new odd subarrays = number of previous even prefix sums.
• When preSum is even, whether it's Odd + Odd or Even + Even, to form an odd subarray, we need to subtract an odd prefix sum. Emulating the mathematical property Odd = Even - Odd, the number of new odd subarrays = number of previous odd prefix sums.

Implementation

python

class Solution:
    def numOfSubarrays(self, arr: List[int]) -> int:
        # Initialization: frequency of odd prefix sums is 0, even prefix sums is 1 (Base case for sum 0)
        odd = 0
        even = 1  # A sum of 0 is even, therefore starting from 1
        ans = 0
        mod = 10**9 + 7  # Modulo constraints defined exactly
        preSum = 0       # Currently running prefix sum scalar 

        # Traverse iterating across entire target array scope 
        for num in arr:
            preSum += num

            # If the current prefix sum is even, it can pair with all prior odd prefix sums to form an odd-sum subarray
            if preSum % 2 == 0:
                ans += odd
                even += 1  # Current evaluated prefix sum qualifies as even; increment statistic
            else:
            # Current prefix sum falls as odd, pairing exclusively backwards matching prior even prefix sums natively  
                ans += even
                odd += 1   # Correspondingly update mapping log indicating new odd discovery occurrences
        
        return ans % mod

javascript

/**
 * @param {number[]} arr
 * @return {number}
 */
var numOfSubarrays = function(arr) {
    let ans = 0;
    let odd = 0;
    let even = 1;
    let preSum = 0;
    const mod = 10 ** 9 + 7;

    for (let num of arr) {
        preSum += num;

        if (preSum % 2 == 0) {
            ans += odd;
            even++;
        } else {
            ans += even;
            odd++;
        }
    }

    return ans % mod;
};

Complexity Analysis

• Time Complexity: O(n) using a single array traversal mapping variables efficiently
• Space Complexity: O(1) requiring only numerical tracking properties maintained iteratively natively

Links

1524. Number of Sub-arrays With Odd Sum (English)1524. 和为奇数的子数组数目 (Chinese)