Skip to content

3247. Number of Subsequences with Odd Sum πŸ”’

Description

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.

 

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 <= 105
  • 1 <= nums[i] <= 109

Solutions

Solution 1: Dynamic Programming

Thinking

Count subsequences whose sum is odd. \(n\le 10^5\) forbids enumeration. Parity of the sum depends only on how many odds were taken, so two rolling states suffice.

\(f[0],f[1]\) are even-sum and odd-sum counts so far. An odd swaps the two classes and adds the singleton; an even lets each class keep or append, and the even class also gains the singleton. The answer is the final odd class.

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 \(\textit{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 \(\textit{nums}\). The space complexity is \(O(1)\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
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]

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

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

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

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

Comments