Skip to content

3247. Number of Subsequences with Odd Sum 👍

  • Time: $O(n)$
  • Space: $O(1)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
 public:
  int subsequenceCount(vector<int>& nums) {
    constexpr int kMod = 1'000'000'007;
    int even = 0;  // the number of subsequences with even sum
    int odd = 0;   // the number of subsequences with odd sum

    for (const int num : nums)
      if (num % 2 == 0) {
        // Appending an even number to a subsequence doesn't change the parity.
        // The even number itself is also a valid subsequence.
        even = (even + even + 1) % kMod;
        odd = (odd + odd) % kMod;
      } else {
        // Appending an odd number to a subsequence changes the parity.
        // The odd number itself is also a valid subsequence.
        const int newEven = (even + odd) % kMod;
        odd = (odd + even + 1) % kMod;
        even = newEven;
      }

    return odd % kMod;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
  public int subsequenceCount(int[] nums) {
    final int MOD = 1_000_000_007;
    int even = 0; // the number of subsequences with even sum
    int odd = 0;  // the number of subsequences with odd sum

    for (final int num : nums)
      if (num % 2 == 0) {
        // Appending an even number to a subsequence doesn't change the parity.
        // The even number itself is also a valid subsequence.
        even = (even + even + 1) % MOD;
        odd = (odd + odd) % MOD;
      } else {
        // Appending an odd number to a subsequence changes the parity.
        // The odd number itself is also a valid subsequence.
        final int newEven = (even + odd) % MOD;
        odd = (odd + even + 1) % MOD;
        even = newEven;
      }

    return odd % MOD;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution:
  def subsequenceCount(self, nums: list[int]) -> int:
    MOD = 1_000_000_007
    even = 0  # the number of subsequences with even sum
    odd = 0  # the number of subsequences with odd sum

    for num in nums:
      if num % 2 == 0:
        # Appending an even number to a subsequence doesn't change the parity.
        # The even number itself is also a valid subsequence.
        even, odd = even + even + 1, odd + odd
      else:
        # Appending an odd number to a subsequence changes the parity.
        # The odd number itself is also a valid subsequence.
        even, odd = even + odd, odd + even + 1

    return odd % MOD