3247. Number of Subsequences with Odd Sum Solution

The problem

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

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

Example 1:

Input: nums = [1,1,1]

Output: 4

Explanation:

The odd-sum subsequences are: [1, 1, 1], [1, 1, 1], [1, 1, 1], [1, 1, 1].

Example 2:

Input: nums = [1,2,2]

Output: 4

Explanation:

The odd-sum subsequences are: [1, 2, 2], [1, 2, 2], [1, 2, 2], [1, 2, 2].

Constraints:

1 <= nums.length <= 10⁵
1 <= nums[i] <= 10⁹

Approach overview

Problem Overview: Given an integer array, count how many subsequences have an odd sum. A subsequence can skip elements but must keep the original order. The key observation is that the parity of the sum (odd or even) depends only on how many odd numbers are included.

Approach 1: Brute Force Enumeration (O(2^n) time, O(1) space)

Generate every possible subsequence and compute its sum. A bitmask from 0 to 2^n - 1 represents which elements are included. For each mask, iterate through the array, accumulate the sum, and check whether the result is odd. This approach demonstrates the definition of subsequences clearly but becomes impractical once n grows beyond ~20 because the number of subsets doubles with each element.

Approach 2: Dynamic Programming with Parity Tracking (O(n) time, O(1) space)

Track two values while iterating through the array: the number of subsequences with even sum and the number with odd sum. When you see an even number, appending it keeps the parity unchanged. When you see an odd number, appending it flips the parity. Update counts accordingly: new odd subsequences come from extending previous even ones with the odd element, while new even subsequences come from extending previous odd ones. This is a classic dynamic programming pattern where the state only depends on the previous step. The algorithm processes each element once and maintains constant memory.

Approach 3: Combinatorics / Parity Counting (O(n) time, O(1) space)

A subsequence has an odd sum if it contains an odd number of odd elements. Count how many numbers are even (e) and how many are odd (o). Any subset of even numbers can be chosen freely (2^e choices). For odd numbers, you must choose an odd-sized subset, which has 2^(o-1) possibilities when o > 0. Multiply these counts to get the total number of valid subsequences. This reasoning relies on simple combinatorics and parity properties rather than iterative state updates.

Recommended for interviews: The dynamic programming approach is what interviewers typically expect. It shows you understand parity transitions and can model the problem with minimal state. Starting with brute force demonstrates baseline reasoning, but reducing it to an O(n) parity-based DP signals strong algorithmic intuition.

Solution

We define f[0] to represent the number of subsequences with an even sum so far, and f[1] to represent the number of subsequences with an odd sum so far. Initially, f[0] = 0 and f[1] = 0.

Traverse the array nums, for each number x:

If x is odd, the update rules for f[0] and f[1] are:

$\begin{aligned} f[0] & = (f[0] + f[1]) bmod 10^9 + 7, \ f[1] & = (f[0] + f[1] + 1) bmod 10^9 + 7. \end{aligned}

That is, the current number of subsequences with an even sum is equal to the previous number of subsequences with an even sum plus the number of subsequences with an odd sum concatenated with the current number x; the current number of subsequences with an odd sum is equal to the previous number of subsequences with an even sum concatenated with the current number x plus the previous number of subsequences with an odd sum, plus one subsequence containing only the current number x.

If x is even, the update rules for f[0] and f[1] are:

\begin{aligned} f[0] & = (f[0] + f[0] + 1) bmod 10^9 + 7, \ f[1] & = (f[1] + f[1]) bmod 10^9 + 7. \end{aligned}

That is, the current number of subsequences with an even sum is equal to the previous number of subsequences with an even sum plus the number of subsequences with an even sum concatenated with the current number x, plus one subsequence containing only the current number x; the current number of subsequences with an odd sum is equal to the previous number of subsequences with an odd sum concatenated with the current number x plus the previous number of subsequences with an odd sum.

Finally, return f[1].

The time complexity is O(n), where n is the length of the array nums. The space complexity is O(1)$.

Python

class Solution:
    def subsequenceCount(self, nums: List[int]) -> int:
        mod = 10**9 + 7
        f = [0] * 2
        for x in nums:
            if x % 2:
                f[0], f[1] = (f[0] + f[1]) % mod, (f[0] + f[1] + 1) % mod
            else:
                f[0], f[1] = (f[0] + f[0] + 1) % mod, (f[1] + f[1]) % mod
        return f[1]

Java

class Solution {
    public int subsequenceCount(int[] nums) {
        final int mod = (int) 1e9 + 7;
        int[] f = new int[2];
        for (int x : nums) {
            int[] g = new int[2];
            if (x % 2 == 1) {
                g[0] = (f[0] + f[1]) % mod;
                g[1] = (f[0] + f[1] + 1) % mod;
            } else {
                g[0] = (f[0] + f[0] + 1) % mod;
                g[1] = (f[1] + f[1]) % mod;
            }
            f = g;
        }
        return f[1];
    }
}

C++

class Solution {
public:
    int subsequenceCount(vector<int>& nums) {
        const int mod = 1e9 + 7;
        vector<int> f(2);
        for (int x : nums) {
            vector<int> g(2);
            if (x % 2 == 1) {
                g[0] = (f[0] + f[1]) % mod;
                g[1] = (f[0] + f[1] + 1) % mod;
            } else {
                g[0] = (f[0] + f[0] + 1) % mod;
                g[1] = (f[1] + f[1]) % mod;
            }
            f = g;
        }
        return f[1];
    }
};

TypeScript

function subsequenceCount(nums: number[]): number {
    const mod = 1e9 + 7;
    let f = [0, 0];
    for (const x of nums) {
        const g = [0, 0];
        if (x % 2 === 1) {
            g[0] = (f[0] + f[1]) % mod;
            g[1] = (f[0] + f[1] + 1) % mod;
        } else {
            g[0] = (f[0] + f[0] + 1) % mod;
            g[1] = (f[1] + f[1]) % mod;
        }
        f = g;
    }
    return f[1];
}

func subsequenceCount(nums []int) int {
	mod := int(1e9 + 7)
	f := [2]int{}
	for _, x := range nums {
		g := [2]int{}
		if x%2 == 1 {
			g[0] = (f[0] + f[1]) % mod
			g[1] = (f[0] + f[1] + 1) % mod
		} else {
			g[0] = (f[0] + f[0] + 1) % mod
			g[1] = (f[1] + f[1]) % mod
		}
		f = g
	}
	return f[1]
}

Try this approach in the editor

Complexity analysis

Approach	Time	Space	When to Use
Brute Force Enumeration	O(2^n)	O(1)	For understanding subsequence generation or when n is very small
Dynamic Programming (Parity Tracking)	O(n)	O(1)	General case and most common interview solution
Combinatorics Counting	O(n)	O(1)	When you recognize the odd/even parity pattern and want a mathematical shortcut

Frequently asked questions

Is Number of Subsequences with Odd Sum easy or hard?

The problem is typically rated Medium. The brute force idea is straightforward, but recognizing the parity relationship and converting it into an O(n) dynamic programming or combinatorics solution requires deeper insight.

Number of Subsequences with Odd Sum Python/Java solution

The standard implementation keeps two variables: evenCount and oddCount. For each element, update them based on parity transitions. The same logic works across Python, Java, C++, Go, and TypeScript since it relies only on integer arithmetic and a single array traversal.

How to solve Number of Subsequences with Odd Sum in O(n)?

Iterate through the array while tracking counts of subsequences with even and odd sums. Adding an even number keeps the parity unchanged, while adding an odd number flips it. Update the counts based on these transitions for each element. This single-pass dynamic programming approach achieves O(n) time and constant space.

What is the best approach for Number of Subsequences with Odd Sum?

The optimal approach uses dynamic programming with parity tracking. Maintain two counters: the number of subsequences with even sums and the number with odd sums. When processing each element, update these counts depending on whether the number is even or odd. This solution runs in O(n) time and O(1) space.

Is Number of Subsequences with Odd Sum asked at Google/Amazon/Meta?

Parity and subsequence counting problems frequently appear in interviews at companies like Amazon, Google, and Meta. Variants involving odd/even sums, subset parity, or combinatorial counting are common in coding rounds because they test dynamic programming and mathematical reasoning.

What data structure is used in Number of Subsequences with Odd Sum?

The problem mainly uses simple counters rather than complex data structures. The core technique is dynamic programming with two variables representing counts of even-sum and odd-sum subsequences while iterating through the array.

What is the time complexity of Number of Subsequences with Odd Sum?

The optimal solution runs in O(n) time because the array is processed once while updating two parity counters. Space complexity is O(1) since only a few integer variables are stored regardless of input size.

Number of Subsequences with Odd Sum solution and explanation

The problem

Approach overview

Solution

Complexity analysis

Frequently asked questions

Comments

Number of Subsequences with Odd Sum solution and explanation

The problem

Approach overview

Solution

Complexity analysis

Frequently asked questions

Comments

Related problems