Is Count Valid Sequences easy or hard?

Count Valid Sequences is generally considered a medium-level dynamic programming problem. The challenge comes from defining the correct state transition and optimizing repeated computations efficiently.

Count Valid Sequences Python/Java solution

Python solutions usually use memoized DFS with functools.cache or iterative DP lists. Java implementations commonly use 2D arrays for tabulation and modular arithmetic to avoid overflow in large counting problems.

How to solve Count Valid Sequences in O(n)?

A fully linear O(n) solution is only possible when transitions can be reduced to constant-time updates per index. Most versions of Count Valid Sequences use O(n * k) dynamic programming, sometimes optimized with prefix sums or state compression.

What is the best approach for Count Valid Sequences?

The best approach is dynamic programming with memoization or bottom-up tabulation. It avoids recomputing identical states and reduces the complexity from exponential time to O(n * k). Prefix sums are often added to optimize transition calculations further.

Is Count Valid Sequences asked at Google/Amazon/Meta?

Dynamic programming sequence-counting problems are common in interviews at Google, Amazon, and Meta. Variants involving transitions, prefix constraints, or combinatorial counting appear frequently in online assessments and onsite rounds.

What data structure is used in Count Valid Sequences?

The main data structures are DP arrays, hash maps for memoization, and prefix sum arrays for fast range transitions. Some optimized solutions also use bitmasks or rolling arrays to reduce memory usage.

What is the time complexity of Count Valid Sequences?

The optimal solution typically runs in O(n * k) time, where n is the sequence length and k is the number of possible states or values. Space complexity ranges from O(k) to O(n * k) depending on whether rolling arrays are used.

Description Hints 4 Solution Video 27:25

4002. Count Valid Sequences

Medium42.5% acceptance

You are given two positive integers n and k.

A valid sequence is a sequence of k positive integers such that:

The sum of all integers in the sequence is equal to n.
The product of all integers in the sequence is even.

Return the number of valid sequences. Since the answer may be very large, return it modulo 10⁹ + 7.

Two sequences are considered different if they differ at any index. For example, [1, 1, 2] and [1, 2, 1] are considered different sequences.

Example 1:

Input: n = 5, k = 3

Output: 3

Explanation:

The sequences of length k = 3 whose sum is 5 are:

Sequence	Product	Parity
`[1, 1, 3]`	`1 * 1 * 3 = 3`	Odd
`[1, 2, 2]`	`1 * 2 * 2 = 4`	Even
`[2, 1, 2]`	`2 * 1 * 2 = 4`	Even
`[2, 2, 1]`	`2 * 2 * 1 = 4`	Even
`[1, 3, 1]`	`1 * 3 * 1 = 3`	Odd
`[3, 1, 1]`	`3 * 1 * 1 = 3`	Odd

There are 3 sequences with an even product, thus the answer is 3.

Example 2:

Input: n = 3, k = 2

Output: 2

Explanation:

The sequences of length k = 2 whose sum is 3 are:

Sequence	Product	Parity
`[1, 2]`	`1 * 2 = 2`	Even
`[2, 1]`	`2 * 1 = 2`	Even

There are 2 sequences with an even product, thus the answer is 2.

Example 3:

Input: n = 5, k = 5

Output: 0

Explanation:

The only possible sequence of length k = 5 whose sum is 5 is [1, 1, 1, 1, 1], which has an odd product. Thus, the answer is 0.

Constraints:

1 <= n <= 5 * 10⁵
1 <= k <= n

Topics

Combinatorics Math

Hints open one at a time

Hint 1

Count all sequences of k positive integers with sum n, then subtract those whose product is odd.

Hint 2

Using stars and bars, the total number of such sequences is C(n - 1, k - 1).

Hint 3

The product is odd exactly when every element is odd. Write each element as 2 * x + 1 and count the resulting non-negative solutions.

Hint 4

If n - k is odd, no sequence consisting entirely of odd integers exists. Otherwise, subtract C((n + k) / 2 - 1, k - 1).

27:25

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

Open solution

LanguageLoading editor…

1class Solution:
2    def countValidSequences(self, n: int, k: int) -> int:
3        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2Case 3

Input

5
3

Input

3
2

Input

5
5

Your code is saved on this device.Solution