Number of Subsequences with Odd Sum - Practice Coding Problems

Number of Subsequences with Odd Sum - Problem

Given an array nums, return the number of subsequences with an odd sum of elements.

A subsequence is a sequence that can be derived from the array by deleting some or no elements without changing the order of the remaining elements.

Since the answer may be very large, return it modulo 10⁹ + 7.

Input & Output

Example 1 — All Odd Numbers

$ Input: nums = [1,3,5]

› Output: 4

💡 Note: The subsequences with odd sums are [1], [3], [5], [1,3,5]. Sums are 1, 3, 5, 9 respectively - all odd. Total count = 4.

Example 2 — Mixed Odd and Even

$ Input: nums = [2,4,6]

› Output: 0

💡 Note: All numbers are even, so any sum will be even. No subsequences can have odd sums. Total count = 0.

Example 3 — Single Odd Element

$ Input: nums = [1,2,4]

› Output: 4

💡 Note: Subsequences with odd sums: [1] (sum=1), [1,2] (sum=3), [1,4] (sum=5), [1,2,4] (sum=7). All contain the single odd number 1. Total count = 4.

Constraints

1 ≤ nums.length ≤ 10⁵
-10⁹ ≤ nums[i] ≤ 10⁹
Answer is returned modulo 10⁹ + 7

Visualization

Tap to expand

Understanding the Visualization

Input Array

Given array with mix of odd and even numbers

Key Insight

Odd sum requires odd number of odd elements

Count Result

Use combinatorics to count valid subsequences

Key Takeaway

🎯 Key Insight: Odd sums require an odd number of odd elements - use combinatorics to count efficiently

Asked in

G Google 15 a Amazon 12 M Microsoft 8 f Facebook 6

The key insight is that a sum is odd if and only if it contains an odd number of odd elements. The optimal approach uses combinatorics: count odd and even elements, then apply the formula 2^(odd_count-1) × 2^even_count. Time: O(n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Dynamic Programming - Count by Parity	O(n)	O(1)	Track count of subsequences with odd and even sums as we process elements
Mathematical Approach - Combinatorics	O(odd_count)	O(1)	Count odd and even numbers, then use combinatorial formula
Brute Force - Generate All Subsequences	O(n × 2^n)	O(1)	Generate all possible subsequences and count those with odd sums

Dynamic Programming - Count by Parity — Algorithm Steps

Initialize odd_count=0, even_count=1 (empty subsequence)
For each element: if odd, swap counts; if even, double both
Add current element as single-element subsequence
Return final odd_count

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize

Start with even_count=1 (empty set), odd_count=0

Process Elements

For each element, update counts based on parity

Final Count

Return the count of odd-sum subsequences

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(int* nums, int n) {
    const int MOD = 1000000007;
    
    // dp[0] = count of subsequences with even sum
    // dp[1] = count of subsequences with odd sum
    long long evenCount = 1;  // empty subsequence has even sum (0)
    long long oddCount = 0;
    
    for (int i = 0; i < n; i++) {
        if (nums[i] % 2 == 1) {  // odd number
            // Adding odd number flips parity
            long long newEven = oddCount;
            long long newOdd = evenCount;
            evenCount = newEven;
            oddCount = newOdd;
        }
        // For even numbers, parity doesn't change
        // Both counts just double (include or exclude this element)
        evenCount = (evenCount * 2) % MOD;
        oddCount = (oddCount * 2) % MOD;
    }
    
    return oddCount;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Parse JSON array manually
    int nums[1000];
    int n = 0;
    
    char* ptr = strchr(line, '[') + 1;
    char* token = strtok(ptr, ",]");
    
    while (token != NULL) {
        nums[n++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    int result = solution(nums, n);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass through array with constant work per element

✓ Linear Growth

Space Complexity

O(1)

Only using two variables to track counts

✓ Linear Space

23.5K Views

Medium Frequency

~25 min Avg. Time

847 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Dynamic Programming - Count by Parity — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler