Welcome to Subscribe On Youtube
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 <= 1051 <= nums[i] <= 109
Solutions
Solution 1: Dynamic Programming
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)$.
-
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]; } } -
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]; } }; -
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] -
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] } -
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]; }