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 Subsequences with Odd Sum

Number: 3537

Difficulty: Medium

Paid? Yes

Companies: N/A

Problem Description

Given an array nums, return the number of subsequences whose sum of elements is odd. The result can be very large, so return it modulo 10^9 + 7.

Key Insights

  • A subsequence’s sum is odd if and only if it contains an odd number of odd elements.
  • The parity of the sum is only affected by odd numbers; even numbers can be included or excluded freely.
  • Count the number of odd and even elements in the array.
  • For the odd elements, half of all possible non-empty subsets have an odd count (i.e., 2^(odd_count - 1) if there is at least one odd).
  • For every combination of odd numbers (which give odd sum), every subset of even numbers (2^(even_count) possibilities) can be paired.
  • If there are no odd numbers in the array, no subsequence can have an odd sum.

Space and Time Complexity

Time Complexity: O(n), where n is the length of nums, because we traverse the array to count odd and even numbers. Space Complexity: O(1), as we only use a constant amount of additional space.

Solution

The solution hinges on splitting the problem into two independent parts: choosing odd elements and choosing even elements.

  1. Traverse the array and count the number of odd elements (odd_count) and even elements (even_count).
  2. If there are no odd elements, return 0 since no odd-sum subsequence can be formed.
  3. The number of ways to choose an odd number of odd elements from odd_count items is 2^(odd_count - 1). This comes from the fact that among all 2^(odd_count) subsets, exactly half have an odd count (since the total sum modulo 2 is evenly distributed when at least one odd exists).
  4. The number of ways to include or exclude even elements is 2^(even_count) (each even can be either taken or not, independent of the sum’s parity).
  5. Multiply the two counts, and take the result modulo 10^9 + 7 using modular exponentiation to handle the large numbers.

This approach efficiently computes the answer with a single pass to count elements and uses fast modular exponentiation for power calculations.

Code Solutions

MOD = 10**9 + 7

def numberOfSubsequencesWithOddSum(nums):
    # Count odd and even numbers
    odd_count = sum(1 for num in nums if num % 2 == 1)
    even_count = len(nums) - odd_count
    
    # If no odd numbers exist, no subsequence can have an odd sum
    if odd_count == 0:
        return 0

    # Calculate power under modulo: 2^(even_count) % MOD
    even_combinations = pow(2, even_count, MOD)
    
    # Calculate power under modulo: 2^(odd_count - 1) % MOD
    odd_combinations = pow(2, odd_count - 1, MOD)
    
    # Multiply both parts to get the total number of valid subsequences
    return (even_combinations * odd_combinations) % MOD

# Example usage:
nums1 = [1, 1, 1]
nums2 = [1, 2, 2]
print(numberOfSubsequencesWithOddSum(nums1))  # Output: 4
print(numberOfSubsequencesWithOddSum(nums2))  # Output: 4
← Back to All Questions