We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Number of Sub-arrays With Odd Sum

Number: 1631

Difficulty: Medium

Paid? No

Companies: Microsoft, Directi

Problem Description

Given an array of integers, the goal is to count the number of subarrays whose sum is odd. Since the result can be very large, return it modulo 10^9 + 7.

Key Insights

  • Use prefix sums and track their parity (even or odd).
  • The difference between two prefix sums gives the subarray sum; it is odd if one prefix sum is even and the other is odd.
  • Maintain a count of even and odd prefix sums while iterating through the array.
  • Modulo arithmetic is applied at every step due to potential high counts.

Space and Time Complexity

Time Complexity: O(n) - We traverse the array once.
Space Complexity: O(1) - Only a few counters are used.

Solution

The approach uses prefix sums and leverages the property that the difference between two prefix sums gives the sum of a subarray. The parity (even/odd) of this difference is odd only if one prefix sum is even and the other is odd. Start by initializing the count of even prefix sums as 1 (to account for a prefix sum of 0). As you iterate, update the current prefix sum and check its parity. If the current prefix sum is even, add the count of odd prefix sums to the result, otherwise add the count of even prefix sums. Finally, update the counters for even or odd prefix sums accordingly. This method ensures an efficient solution with a single pass through the array.

Code Solutions

# Define the modulo constant
MOD = 10**9 + 7

# Python solution using prefix sum and parity counts
class Solution:
    def numOfSubarrays(self, arr: List[int]) -> int:
        # Initialize counts for even and odd prefix sums.
        even_count = 1  # Account for the prefix sum of 0 (even)
        odd_count = 0
        prefix_sum = 0
        result = 0
        
        # Iterate over each number in the array
        for num in arr:
            prefix_sum += num  # Update the prefix sum
            
            # Check if the current prefix sum is even or odd
            if prefix_sum % 2 == 0:
                # If even, subarray sum is odd if previous prefix was odd
                result = (result + odd_count) % MOD
                even_count += 1  # Increment count for even prefix sum
            else:
                # If odd, subarray sum is odd if previous prefix was even
                result = (result + even_count) % MOD
                odd_count += 1  # Increment count for odd prefix sum
        return result
← Back to All Questions