Count Valid Sequences solution and explanation
5 more videos on this problem
Leetcode 4002 | Count Valid Sequences | Leetcode weekly contest 512 | Maths | CombinatoricsCodeWithMeGuys · 27:25 · 527 views
LeetCode 4002 | Count Valid Sequences | Math + Combinatorics | JavaCode Kage · 20:22 · 308 views
LeetCode 4002 | Weekly Contest 512 Q3 | Count Valid Sequences | Math + Stars and Bars 🤔CodeSprint · 33:46 · 266 views
Count Valid Sequences | Leetcode 4002 | Number ThoeryTechdose · 23:33 · 219 views
Leetcode contest 512 - 4002 - Count Valid SubsequencesManjeet Dhayal · 22:30 · 134 views
4002. Count Valid Sequences | LeetCode Weekly 512 | Maths | Combinatorics with Proof and ExplanationBEASTCODES · 23:08 · 66 views
The problem
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 109 + 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 * 1051 <= k <= n
Approach overview
Problem Overview: You need to count how many sequences satisfy a set of validity rules while processing elements in order. Most solutions fail because they recompute the same states repeatedly or ignore how previous choices affect future positions.
Approach 1: Brute Force Backtracking (Exponential Time)
The direct solution generates every possible sequence and checks whether it satisfies the constraints. You recursively place each candidate value, validate the partial sequence, then continue to the next index. This approach is useful for understanding the state transitions and testing small inputs, but the branching factor grows quickly. Time complexity is O(k^n) in the worst case, and space complexity is O(n) from recursion depth.
Approach 2: Top-Down Dynamic Programming with Memoization (O(n * k))
Instead of recomputing the same subproblems, cache results using a memo table keyed by the current index and previous state. Each recursive call represents the number of valid continuations from that position. The key insight is that future choices depend only on a limited amount of prior information, which makes the problem a strong fit for dynamic programming. This reduces repeated work dramatically. Time complexity becomes O(n * k), while space complexity is O(n * k) for the cache and recursion stack.
Approach 3: Bottom-Up DP with Prefix Sum Optimization (O(n * k))
The optimal implementation builds the DP table iteratively instead of using recursion. For each position, compute the number of valid transitions from earlier states. If the transition range is large, maintain running totals using a prefix sum array so each state update becomes constant time instead of iterating over all previous values. This removes recursion overhead and performs better on large constraints. Time complexity stays O(n * k), but the constant factors are lower. Space complexity is O(k) when only the previous row is stored.
Approach 4: State Compression DP (O(n * k))
If the state contains multiple dimensions, you can compress it into a smaller representation using bitmasks or rolling arrays. This is common when the sequence rules depend on adjacent values or parity conditions. Combining compressed states with iterative transitions gives better cache locality and lower memory usage. This approach often appears alongside array-based DP optimizations in interview settings.
Recommended for interviews: Interviewers usually expect the dynamic programming solution with memoization or iterative tabulation. Showing the brute force approach first demonstrates that you understand the search space. Transitioning to cached states and prefix sum optimization shows that you can identify overlapping subproblems and reduce unnecessary computation.
Solution
The number of ordered ways to write n as a sum of k positive integers is \binom{n-1}{k-1}. An even product means "at least one even number"; the complement is "all odd".
Therefore the answer is:
$
\binom{n-1}{k-1} - (number of all-odd sequences)
If every number is odd, write the i-th number as 2a_i + 1 (a_i \ge 0). Then:
sum_{i=1}^{k}(2a_i + 1) = n \implies sum_{i=1}^{k} a_i = \frac{n-k}{2}
All-odd sequences exist only when n and k have the same parity (i.e., n + k is even), and their count is \binom{\frac{n+k}{2}-1}{k-1}; otherwise the count is 0.
After precomputing factorials and modular inverses, each combination can be evaluated in O(1). Return the answer modulo 10^9+7.
The time complexity is O(N + log M) for preprocessing, and the space complexity is O(N), where N = 5 times 10^5 and M = 10^9+7. Each query is O(1)$.
MX = 5 * 10**5 + 1
MOD = 10**9 + 7
f = [1] * MX
g = [1] * MX
for i in range(1, MX):
f[i] = f[i - 1] * i % MOD
g[i] = pow(f[i], MOD - 2, MOD)
def comb(n: int, k: int) -> int:
return f[n] * g[k] * g[n - k] % MOD
class Solution:
def countValidSequences(self, n: int, k: int) -> int:
ans = comb(n - 1, k - 1)
if (n + k) % 2 == 0:
ans = (ans - comb((n + k) // 2 - 1, k - 1)) % MOD
return ansclass Solution {
static final int MX = 500001;
static final long MOD = 1000000007L;
static long[] f = new long[MX];
static long[] g = new long[MX];
static {
f[0] = 1;
g[0] = 1;
for (int i = 1; i < MX; i++) {
f[i] = f[i - 1] * i % MOD;
g[i] = pow(f[i], MOD - 2);
}
}
static long pow(long a, long b) {
long res = 1;
while (b > 0) {
if ((b & 1) == 1) {
res = res * a % MOD;
}
a = a * a % MOD;
b >>= 1;
}
return res;
}
static long comb(int n, int k) {
return f[n] * g[k] % MOD * g[n - k] % MOD;
}
public int countValidSequences(int n, int k) {
long ans = comb(n - 1, k - 1);
if ((n + k) % 2 == 0) {
ans = (ans - comb((n + k) / 2 - 1, k - 1) + MOD) % MOD;
}
return (int) ans;
}
}const int MX = 500001;
const long long MOD = 1000000007LL;
long long f[MX];
long long g[MX];
long long qpow(long long a, long long b) {
long long res = 1;
while (b > 0) {
if (b & 1) {
res = res * a % MOD;
}
a = a * a % MOD;
b >>= 1;
}
return res;
}
int init = []() {
f[0] = 1;
g[0] = 1;
for (int i = 1; i < MX; i++) {
f[i] = f[i - 1] * i % MOD;
g[i] = qpow(f[i], MOD - 2);
}
return 0;
}();
long long comb(int n, int k) {
return f[n] * g[k] % MOD * g[n - k] % MOD;
}
class Solution {
public:
int countValidSequences(int n, int k) {
long long ans = comb(n - 1, k - 1);
if ((n + k) % 2 == 0) {
ans = (ans - comb((n + k) / 2 - 1, k - 1) + MOD) % MOD;
}
return (int) ans;
}
};const MX = 500001;
const MOD = 1000000007n;
const f: bigint[] = new Array(MX).fill(1n);
const g: bigint[] = new Array(MX).fill(1n);
function pow(a: bigint, b: bigint): bigint {
let res = 1n;
while (b > 0n) {
if (b & 1n) {
res = (res * a) % MOD;
}
a = (a * a) % MOD;
b >>= 1n;
}
return res;
}
for (let i = 1; i < MX; i++) {
f[i] = (f[i - 1] * BigInt(i)) % MOD;
g[i] = pow(f[i], MOD - 2n);
}
function comb(n: number, k: number): bigint {
return (((f[n] * g[k]) % MOD) * g[n - k]) % MOD;
}
function countValidSequences(n: number, k: number): number {
let ans = comb(n - 1, k - 1);
if ((n + k) % 2 === 0) {
ans = (ans - comb((n + k) / 2 - 1, k - 1) + MOD) % MOD;
}
return Number(ans);
}const MX = 500001
const MOD int64 = 1000000007
var f [MX]int64
var g [MX]int64
func init() {
f[0] = 1
g[0] = 1
for i := 1; i < MX; i++ {
f[i] = f[i-1] * int64(i) % MOD
g[i] = pow(f[i], MOD-2)
}
}
func pow(a, b int64) int64 {
res := int64(1)
for b > 0 {
if b&1 == 1 {
res = res * a % MOD
}
a = a * a % MOD
b >>= 1
}
return res
}
func comb(n, k int) int64 {
return f[n] * g[k] % MOD * g[n-k] % MOD
}
func countValidSequences(n int, k int) int {
ans := comb(n-1, k-1)
if (n+k)%2 == 0 {
ans = (ans - comb((n+k)/2-1, k-1) + MOD) % MOD
}
return int(ans)
}Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Backtracking | O(k^n) | O(n) | Small inputs or validating transition logic |
| Top-Down DP with Memoization | O(n * k) | O(n * k) | General case with overlapping subproblems |
| Bottom-Up DP + Prefix Sums | O(n * k) | O(k) | Large constraints and performance-sensitive cases |
| State Compression DP | O(n * k) | O(k) | Complex state transitions with memory constraints |
Frequently asked questions
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.