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:

1
2
3
4
5

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:

1
2
3
4
5

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

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;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

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
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

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);
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

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()
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

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
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

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
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

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)