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)$.
Python3ο
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];
}
};
Goο
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]
}
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];
}