Number of Subsequences with Odd Sum

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 109 + 7.

Examples

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^5
• 1 <= nums[i] <= 10^9

Solution

Method 1 – Combinatorics and Parity DP

Intuition

For each number, we can either include it or not in a subsequence. We can use dynamic programming to keep track of the number of subsequences with even and odd sums. For each number, if we add it to an even-sum subsequence, the parity flips if the number is odd, otherwise it stays the same.

Approach

1. Initialize even = 1 (empty subsequence), odd = 0.
2. For each num in nums:
   • If num is even: even, odd = even2, odd2
   • If num is odd: even, odd = even+odd, even+odd
3. Subtract 1 from even at the end to exclude the empty subsequence.
4. Return odd modulo 1e9+7.

Code

C++

class Solution {
public:
    int countOddSumSubsequences(vector<int>& nums) {
        const int MOD = 1e9+7;
        long even = 1, odd = 0;
        for (int x : nums) {
            if (x % 2 == 0) {
                even = (even * 2) % MOD;
                odd = (odd * 2) % MOD;
            } else {
                long neven = (even + odd) % MOD;
                long nodd = (even + odd) % MOD;
                even = neven;
                odd = nodd;
            }
        }
        return (odd + MOD) % MOD;
    }
};

Go

func countOddSumSubsequences(nums []int) int {
    mod := int(1e9+7)
    even, odd := 1, 0
    for _, x := range nums {
        if x%2 == 0 {
            even = even * 2 % mod
            odd = odd * 2 % mod
        } else {
            neven := (even + odd) % mod
            nodd := (even + odd) % mod
            even, odd = neven, nodd
        }
    }
    return (odd + mod) % mod
}

Java

class Solution {
    public int countOddSumSubsequences(int[] nums) {
        int MOD = 1_000_000_007;
        long even = 1, odd = 0;
        for (int x : nums) {
            if (x % 2 == 0) {
                even = even * 2 % MOD;
                odd = odd * 2 % MOD;
            } else {
                long neven = (even + odd) % MOD;
                long nodd = (even + odd) % MOD;
                even = neven;
                odd = nodd;
            }
        }
        return (int)((odd + MOD) % MOD);
    }
}

Kotlin

class Solution {
    fun countOddSumSubsequences(nums: IntArray): Int {
        val MOD = 1_000_000_007
        var even = 1L
        var odd = 0L
        for (x in nums) {
            if (x % 2 == 0) {
                even = even * 2 % MOD
                odd = odd * 2 % MOD
            } else {
                val neven = (even + odd) % MOD
                val nodd = (even + odd) % MOD
                even = neven
                odd = nodd
            }
        }
        return ((odd + MOD) % MOD).toInt()
    }
}

Python

class Solution:
    def countOddSumSubsequences(self, nums: list[int]) -> int:
        MOD = 10**9 + 7
        even, odd = 1, 0
        for x in nums:
            if x % 2 == 0:
                even = even * 2 % MOD
                odd = odd * 2 % MOD
            else:
                neven = (even + odd) % MOD
                nodd = (even + odd) % MOD
                even, odd = neven, nodd
        return odd % MOD

Rust

impl Solution {
    pub fn count_odd_sum_subsequences(nums: Vec<i32>) -> i32 {
        let m = 1_000_000_007;
        let (mut even, mut odd) = (1i64, 0i64);
        for &x in &nums {
            if x % 2 == 0 {
                even = even * 2 % m;
                odd = odd * 2 % m;
            } else {
                let neven = (even + odd) % m;
                let nodd = (even + odd) % m;
                even = neven;
                odd = nodd;
            }
        }
        (odd + m) as i32 % m
    }
}

TypeScript

class Solution {
    countOddSumSubsequences(nums: number[]): number {
        const MOD = 1e9+7
        let even = 1, odd = 0
        for (const x of nums) {
            if (x % 2 === 0) {
                even = even * 2 % MOD
                odd = odd * 2 % MOD
            } else {
                const neven = (even + odd) % MOD
                const nodd = (even + odd) % MOD
                even = neven
                odd = nodd
            }
        }
        return odd % MOD
    }
}

Complexity

• ⏰ Time complexity: O(n)
• 🧺 Space complexity: O(1)