Is Number of Subsequences with Odd Sum easy or hard?

The problem is typically rated Medium. The brute force idea is straightforward, but recognizing the parity relationship and converting it into an O(n) dynamic programming or combinatorics solution requires deeper insight.

Number of Subsequences with Odd Sum Python/Java solution

The standard implementation keeps two variables: evenCount and oddCount. For each element, update them based on parity transitions. The same logic works across Python, Java, C++, Go, and TypeScript since it relies only on integer arithmetic and a single array traversal.

How to solve Number of Subsequences with Odd Sum in O(n)?

Iterate through the array while tracking counts of subsequences with even and odd sums. Adding an even number keeps the parity unchanged, while adding an odd number flips it. Update the counts based on these transitions for each element. This single-pass dynamic programming approach achieves O(n) time and constant space.

What is the best approach for Number of Subsequences with Odd Sum?

The optimal approach uses dynamic programming with parity tracking. Maintain two counters: the number of subsequences with even sums and the number with odd sums. When processing each element, update these counts depending on whether the number is even or odd. This solution runs in O(n) time and O(1) space.

Is Number of Subsequences with Odd Sum asked at Google/Amazon/Meta?

Parity and subsequence counting problems frequently appear in interviews at companies like Amazon, Google, and Meta. Variants involving odd/even sums, subset parity, or combinatorial counting are common in coding rounds because they test dynamic programming and mathematical reasoning.

What data structure is used in Number of Subsequences with Odd Sum?

The problem mainly uses simple counters rather than complex data structures. The core technique is dynamic programming with two variables representing counts of even-sum and odd-sum subsequences while iterating through the array.

What is the time complexity of Number of Subsequences with Odd Sum?

The optimal solution runs in O(n) time because the array is processed once while updating two parity counters. Space complexity is O(1) since only a few integer variables are stored regardless of input size.

Description Hints 6 Solution Video 8:52

3247. Number of Subsequences with Odd Sum

Medium47.6% acceptancePremium elsewhere, free here

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 10⁹ + 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 <= 10⁵
1 <= nums[i] <= 10⁹

Topics

Hints open one at a time

Hint 1

Define dp[i][0] as the answer for the subarray [0, i].

Hint 2

Similarly define dp[i][1] as the answer for the subarray [0, i] if we wanted to count even-sum subsequences.

Hint 3

If nums[i] is odd, dp[i][x] = 2ⁱ.

Hint 4

Otherwise, dp[i][x] = dp[i - 1][x] * 2.

Hint 5

dp[0][1] = 1 if nums[0] is odd, and 0 otherwise.

Hint 6

dp[0][0] = 2 if nums[0] is even, and 1 otherwise (since an empty subsequence has an even sum).

8:52

Still stuck?Read the written solution, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
  def solve(self):
      pass


Starter codePython 3Spaces: 4

Examples

Case 1Case 2

Input

[1,1,1]

Input

[1,2,2]

Your code is saved on this device.Solution