LeetCode 3247 - Number of Subsequences with Odd Sum

The problem asks us to count how many subsequences of the given array have an odd sum. A subsequence is formed by choosing any subset of elements while preserving their original order. Unlike subarrays, subsequences do not need to be contiguous.

leetcodemediumarraymathdynamic-programmingcombinatorics

LeetCode Problem 3247

Difficulty: 🟡 Medium
Topics: Array, Math, Dynamic Programming, Combinatorics

Solution

Problem Understanding

The problem asks us to count how many subsequences of the given array have an odd sum.

A subsequence is formed by choosing any subset of elements while preserving their original order. Unlike subarrays, subsequences do not need to be contiguous. For an array of length n, there are 2^n total subsequences, including the empty subsequence.

We only care about subsequences whose sum of elements is odd. Since the total number of subsequences can become extremely large, the answer must be returned modulo 10^9 + 7.

The input consists of:

  • nums, an integer array
  • 1 <= nums.length <= 10^5
  • 1 <= nums[i] <= 10^9

The large constraint on nums.length immediately tells us that any exponential approach is impossible. Even an O(n^2) solution would be too slow for 10^5 elements. We need a linear or near-linear algorithm.

The most important observation is that only the parity of each number matters:

  • Even numbers do not change parity when added
  • Odd numbers flip parity when added

For example:

  • even + even = even
  • even + odd = odd
  • odd + odd = even

This means we do not need the actual sums, only whether the current sum is even or odd.

Some important edge cases include:

  • Arrays containing only even numbers, where no odd-sum subsequence exists
  • Arrays containing only odd numbers, where many subsequences become odd
  • Arrays of size 1
  • Very large arrays, where efficiency and modulo handling become essential

The problem guarantees all values are positive integers, so we never need to deal with negative parity behavior.

Approaches

Brute Force Approach

The brute force solution generates every possible subsequence, computes its sum, and checks whether that sum is odd.

Since each element can either be included or excluded, there are 2^n possible subsequences. For each subsequence, we may need up to O(n) work to compute its sum.

This approach is correct because it explicitly checks every possible subsequence and counts exactly those whose sum is odd.

However, it is far too slow for n = 10^5.

For example:

  • n = 20 already gives over one million subsequences
  • n = 50 gives more than one quadrillion subsequences

Therefore, brute force is computationally infeasible.

Optimal Dynamic Programming Approach

The key insight is that we only need to track parity.

At any point while processing the array, every subsequence belongs to one of two categories:

  • subsequences with even sum
  • subsequences with odd sum

We maintain two counts:

  • even_count
  • odd_count

When we process a new number:

  • If the number is even:

  • adding it preserves parity

  • even subsequences stay even

  • odd subsequences stay odd

  • If the number is odd:

  • adding it flips parity

  • even subsequences become odd

  • odd subsequences become even

This allows us to update the counts in constant time per element.

Because we only store two integers and process the array once, the solution becomes extremely efficient.

Approach Time Complexity Space Complexity Notes
Brute Force O(n × 2^n) O(2^n) Generates all subsequences
Optimal O(n) O(1) Tracks counts of even and odd subsequences

Algorithm Walkthrough

  1. Initialize two counters:
  • even_count = 1
  • odd_count = 0

We start with one even subsequence, the empty subsequence whose sum is 0. 2. Iterate through each number in nums. 3. If the current number is even:

  • Every existing even subsequence can either:

  • ignore the number

  • include the number

  • Both choices remain even.

Similarly, every odd subsequence remains odd.

Therefore:

  • new_even = even_count * 2
  • new_odd = odd_count * 2
  1. If the current number is odd:
  • Adding it flips parity.
  • Existing even subsequences become odd when including the number.
  • Existing odd subsequences become even when including the number.

The updates become:

  • new_even = even_count + odd_count
  • new_odd = even_count + odd_count
  1. Apply modulo 10^9 + 7 after each update to avoid overflow.
  2. Continue until all elements are processed.
  3. Return odd_count, which represents the number of subsequences with odd sum.

Why it works

The algorithm maintains the invariant that after processing the first i elements:

  • even_count equals the number of subsequences with even sum
  • odd_count equals the number of subsequences with odd sum

Every new element either preserves parity, if even, or flips parity, if odd. Since every subsequence either includes or excludes the current element, the transitions account for all possibilities exactly once. Therefore, after processing the entire array, odd_count is the correct answer.

Python Solution

from typing import List

class Solution:
    def subsequenceCount(self, nums: List[int]) -> int:
        MOD = 10**9 + 7
        
        even_count = 1
        odd_count = 0
        
        for num in nums:
            if num % 2 == 0:
                even_count = (even_count * 2) % MOD
                odd_count = (odd_count * 2) % MOD
            else:
                total = (even_count + odd_count) % MOD
                even_count = total
                odd_count = total
        
        return odd_count

The implementation directly follows the dynamic programming logic described earlier.

We initialize even_count to 1 because the empty subsequence has an even sum of 0. Initially, there are no odd-sum subsequences.

For each number:

  • If the number is even, parity does not change when adding it to an existing subsequence. Therefore, both counts simply double.
  • If the number is odd, parity flips when including the number, so both new counts become the total number of previous subsequences.

The modulo operation is applied during updates to ensure values stay within bounds.

Finally, the method returns odd_count, which represents all odd-sum subsequences.

Go Solution

func subsequenceCount(nums []int) int {
    const MOD int = 1e9 + 7

    evenCount := 1
    oddCount := 0

    for _, num := range nums {
        if num%2 == 0 {
            evenCount = (evenCount * 2) % MOD
            oddCount = (oddCount * 2) % MOD
        } else {
            total := (evenCount + oddCount) % MOD
            evenCount = total
            oddCount = total
        }
    }

    return oddCount
}

The Go implementation is structurally identical to the Python version.

Go requires explicit integer declarations, so we define MOD as an integer constant. Since the values remain within modulo bounds throughout execution, standard int arithmetic is sufficient on LeetCode's platform.

The algorithm still uses constant extra space and processes the array in a single pass.

Worked Examples

Example 1

Input:

nums = [1, 1, 1]

Initial state:

Step Number even_count odd_count
Start - 1 0

Process first 1:

  • Odd number
  • total = 1 + 0 = 1
Step Number even_count odd_count
1 1 1 1

Process second 1:

  • Odd number
  • total = 1 + 1 = 2
Step Number even_count odd_count
2 1 2 2

Process third 1:

  • Odd number
  • total = 2 + 2 = 4
Step Number even_count odd_count
3 1 4 4

Final answer:

4

Example 2

Input:

nums = [1, 2, 2]

Initial state:

Step Number even_count odd_count
Start - 1 0

Process 1:

  • Odd number
  • total = 1
Step Number even_count odd_count
1 1 1 1

Process 2:

  • Even number
  • Counts double
Step Number even_count odd_count
2 2 2 2

Process second 2:

  • Even number
  • Counts double again
Step Number even_count odd_count
3 2 4 4

Final answer:

4

Complexity Analysis

Measure Complexity Explanation
Time O(n) Single pass through the array
Space O(1) Only two counters are stored

The algorithm processes each element exactly once and performs only constant-time operations during each iteration. No additional arrays, maps, or recursion are used, so the auxiliary space remains constant.

Test Cases

from typing import List

class Solution:
    def subsequenceCount(self, nums: List[int]) -> int:
        MOD = 10**9 + 7
        
        even_count = 1
        odd_count = 0
        
        for num in nums:
            if num % 2 == 0:
                even_count = (even_count * 2) % MOD
                odd_count = (odd_count * 2) % MOD
            else:
                total = (even_count + odd_count) % MOD
                even_count = total
                odd_count = total
        
        return odd_count

sol = Solution()

assert sol.subsequenceCount([1, 1, 1]) == 4  # all odd numbers
assert sol.subsequenceCount([1, 2, 2]) == 4  # one odd, two evens
assert sol.subsequenceCount([2, 4, 6]) == 0  # all even numbers
assert sol.subsequenceCount([1]) == 1        # single odd element
assert sol.subsequenceCount([2]) == 0        # single even element
assert sol.subsequenceCount([1, 3]) == 2     # two odd subsequences
assert sol.subsequenceCount([1, 2]) == 2     # odd subsequences double with even
assert sol.subsequenceCount([1, 1, 2]) == 4 # mixed parity
assert sol.subsequenceCount([5, 7, 9, 11]) == 8  # all odd values
assert sol.subsequenceCount([10**9] * 5) == 0    # large even values
Test Why
[1,1,1] Verifies repeated odd parity flips
[1,2,2] Verifies even numbers preserve parity
[2,4,6] Ensures no odd subsequences exist
[1] Smallest odd input
[2] Smallest even input
[1,3] Tests multiple odd elements
[1,2] Ensures even numbers double counts
[1,1,2] Mixed parity interaction
[5,7,9,11] Larger all-odd scenario
[10^9,10^9,10^9,10^9,10^9] Large even values, parity-only logic

Edge Cases

All Numbers Are Even

An array like [2, 4, 6, 8] is an important edge case because adding even numbers never changes parity. Every subsequence sum remains even, so the correct answer is 0.

A buggy implementation might accidentally count the empty subsequence or mishandle parity transitions. This solution correctly keeps odd_count at zero throughout processing.

Single Element Arrays

Arrays of length one are common sources of off-by-one errors.

For [1], the only non-empty subsequence is odd, so the answer is 1.

For [2], the only non-empty subsequence is even, so the answer is 0.

The initialization with even_count = 1 correctly represents the empty subsequence and allows these minimal cases to work naturally.

Large Inputs

The constraint allows up to 10^5 elements, meaning the number of subsequences grows astronomically large.

Without modulo operations, integer overflow would occur quickly. The implementation applies modulo arithmetic after every update, ensuring correctness even for massive inputs.

The linear runtime also guarantees the solution remains efficient at maximum input size.