Problem Informations

• Problem Index: 1524
• Problem Link: Number of Sub-arrays With Odd Sum
• Topics: Array, Math, Dynamic Programming, Prefix Sum

Problem Description

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

Constraints:

• $1 \leq arr.length \leq 10^5$
• $1 \leq arr[i] \leq 100$

Intuition

The problem requires counting the number of subarrays with an odd sum from a given array of integers. A subarray is defined as a contiguous part of an array. The challenge is mainly about efficiently determining the number of subarrays with odd sums since brute force methods would not be feasible given the constraints. The intuition here is to leverage the properties of prefix sums, enabling us to calculate the sum of any subarray using previously computed sums. The key observation is that the sum of a subarray can be expressed in terms of prefix sums. Specifically, the sum of elements between indices $i$ and $j$ is odd if and only if the difference between their respective prefix sums is odd.

Approach

The approach starts with initializing counters to keep track of how many prefix sums are odd and even. We denote oddCount as the number of prefix subarrays with an odd sum and evenCount as the number with an even sum. Initially, there is one empty prefix with an even sum (hence, evenCount = 1).

The algorithm proceeds as follows:

1. Iterate over each element of the array arr.
2. We maintain a boolean variable isPrefixOdd to denote whether the current prefix sum is odd. It is updated at each step by XOR-ing with the parity (odd/even nature) of the current element.
3. If isPrefixOdd is true, it indicates that the current running prefix sum is odd:
   • Add the count of previous even sums (evenCount) to the answer because pairing a new odd prefix with an old even one results in an odd subarray sum.
   • Increment the oddCount since we’ve encountered a new odd prefix sum.
4. If isPrefixOdd is false, the current prefix sum is even:
   • Add the count of previous odd sums (oddCount) to the answer. Pairing a new even prefix with an old odd one results in an odd subarray sum.
   • Increment the evenCount since we’ve encountered a new even prefix sum.
5. Since the result can be large, ensure it does not exceed $10^9 + 7$ by taking modulo at each step.
6. Return the total count of subarrays with odd sums stored in ans.

This method ensures we efficiently count the subarrays without explicitly calculating every possible subarray sum, thus handling the problem within the constraints.

Code

C++

#define MAX 1000000007

class Solution {
public:
    int numOfSubarrays(vector<int>& arr) {
        int len = arr.size();
        int ans = 0;          // To store the total number of subarrays with an odd sum
        int oddCount = 0;     // Count of prefix subarrays with an odd sum
        int evenCount = 1;    // Count of prefix subarrays with an even sum; initialized to 1 for the initial prefix
        bool isPrefixOdd = false;  // Boolean to track if the current prefix sum is odd

        // Iterate through each element in the array
        for (int num : arr) {
            // Update the prefix odd status based on the current element
            isPrefixOdd ^= (num & 1);
            
            if (isPrefixOdd) {
                ans += evenCount;  // If current prefix sum is odd, add even prefix count to answer
                oddCount++;        // Increment the count of odd prefix subarrays
            } else {
                ans += oddCount;   // If current prefix sum is even, add odd prefix count to answer
                evenCount++;       // Increment the count of even prefix subarrays
            }
            
            // Ensure the answer is within the limit by applying modulo
            if (ans >= MAX) {
                ans -= MAX;
            }
        }
        
        return ans;
    }
};

Python

class Solution:
    def numOfSubarrays(self, arr):
        MAX = 1000000007
        len_arr = len(arr)
        ans = 0          # To store the total number of subarrays with an odd sum
        oddCount = 0     # Count of prefix subarrays with an odd sum
        evenCount = 1    # Count of prefix subarrays with an even sum; initialized to 1 for the initial prefix
        isPrefixOdd = False  # Boolean to track if the current prefix sum is odd

        # Iterate through each element in the array
        for num in arr:
            # Update the prefix odd status based on the current element
            isPrefixOdd ^= (num & 1)
            
            if isPrefixOdd:
                ans += evenCount  # If current prefix sum is odd, add even prefix count to answer
                oddCount += 1     # Increment the count of odd prefix subarrays
            else:
                ans += oddCount   # If current prefix sum is even, add odd prefix count to answer
                evenCount += 1    # Increment the count of even prefix subarrays
            
            # Ensure the answer is within the limit by applying modulo
            if ans >= MAX:
                ans -= MAX
        
        return ans

Complexity

• Time complexity: $O(n)$

  The algorithm iterates over the array arr exactly once, performing constant-time operations for each element. The iteration through the array takes linear time relative to the size of the array, $n$. Thus, the time complexity is $O(n)$.

• Space complexity: $O(1)$

  The algorithm uses a fixed amount of extra space, independent of the size of the input array. It maintains a few integer variables (ans, oddCount, evenCount) and a boolean (isPrefixOdd). Since this space does not scale with the input size, the space complexity is $O(1)$.