4002 LeetCode problem solution

LeetCode problem link: 4002. Count Valid Sequences

LeetCode 4002 problem description

Medium level 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 10⁹ + 7.

Two sequences are considered different if they differ at any index.

Example 1:

Input: n = 5, k = 3
Output: 3

Explanation: [1, 2, 2], [2, 1, 2], and [2, 2, 1] have an even product.

Example 2:

Input: n = 3, k = 2
Output: 2

Explanation: The valid sequences are [1, 2] and [2, 1].

Example 3:

Input: n = 5, k = 5
Output: 0

Explanation: The only possible sequence is [1, 1, 1, 1, 1], whose product is odd.

Constraints:

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

LeetCode 4002 problem: solution explanation

This problem can be solved using Combinatorics + Complement Counting.

Instead of directly counting sequences whose product is even, it is easier to count all possible sequences and subtract the sequences whose product is odd:

all sequences - sequences with an odd product

A product is odd only when every number in the sequence is odd. Therefore, every other sequence contains at least one even number and has an even product.

Step 1: Count all sequences

We need to split n into k positive integers:

x1 + x2 + ... + xk = n

Using the combinatorial Stars and Bars method, we count the number of ways to represent n as a sum of k positive integers.

For example, if:

n = 5
k = 3

we need to find all solutions of:

x1 + x2 + x3 = 5

where every number is positive.

The possible sequences are:

1 + 1 + 3
1 + 2 + 2
1 + 3 + 1
2 + 1 + 2
2 + 2 + 1
3 + 1 + 1

There are 6 possible sequences.

We can imagine n = 5 as five stars:

* * * * *

To divide them into k = 3 non-empty groups, we need k - 1 = 2 separators.

For example:

* | * * | * *

represents:

1 + 2 + 2

There are n - 1 = 4 possible positions between the stars:

* _ * _ * _ * _ *

We need to choose k - 1 = 2 of these positions for the separators:

C(4, 2) = 6

Here, C(N, R) represents a combination - the number of ways to choose R elements from N elements without considering their order.

For example:

C(4, 2) = 6

This means there are 6 ways to choose 2 elements from 4.

In general, there are n - 1 positions between n stars, and we need to choose k - 1 positions for the separators.

Therefore, the total number of sequences is:

C(n - 1, k - 1)

Step 2: Count sequences containing only odd numbers

Now we need to count the sequences whose product is odd.

A product is odd only if all k numbers are odd.

Every positive odd number can be written as:

xi = 2 * ai + 1

where:

ai >= 0

Substituting this into:

x1 + x2 + ... + xk = n

gives:

(2 * a1 + 1) + (2 * a2 + 1) + ... + (2 * ak + 1) = n

After simplifying:

2 * (a1 + a2 + ... + ak) + k = n

Therefore:

a1 + a2 + ... + ak = (n - k) / 2

This is possible only when n - k is even. In other words, n and k must have the same parity.

Now ai can be 0, so we use the Stars and Bars formula for non-negative integers:

C(m + k - 1, k - 1)

where:

m = (n - k) / 2

Substituting m gives:

C((n - k) / 2 + k - 1, k - 1)

which simplifies to:

C((n + k) / 2 - 1, k - 1)

Therefore, we first calculate:

answer = C(n - 1, k - 1)

and if n - k is even, subtract the sequences containing only odd numbers:

answer -= C((n + k) / 2 - 1, k - 1)

Step 3: Calculate combinations efficiently

We only need to calculate two binomial coefficients, so there is no need to precompute factorials and inverse factorials for every value up to n.

For a combination:

C(N, R)

N represents the total number of elements, while R represents the number of elements we choose.

Combinations have the following property:

C(N, R) = C(N, N - R)

For example:

C(10, 8) = C(10, 2)

Instead of performing 8 iterations, we only need 2.

That is why we use:

R = min(R, N - R);

For this example:

R = min(8, 10 - 8)
R = min(8, 2)
R = 2

This does not change the result, but reduces the number of calculations.

We then calculate the combination multiplicatively:

C(N, R) = N * (N - 1) * ... * (N - R + 1)
          ------------------------------
                 1 * 2 * ... * R

Because division cannot be performed directly under modulo 10⁹ + 7, we use modular inverses.

Instead of calculating every modular inverse separately with modular exponentiation, we precompute all inverses only up to the largest R that we actually need:

inv[i] = MOD - (MOD / i) * inv[MOD % i] % MOD;

Then each combination can be built incrementally:

result = result * (N - R + i) % MOD;
result = result * inv[i] % MOD;

This avoids building factorial and inverse factorial arrays for every value up to n and reduces the amount of unnecessary preprocessing.

LeetCode 4002 problem: complexity

Let r1 and r2 be the smaller sides of the two combinations after applying:

R = min(R, N - R);

We precompute modular inverses only up to:

max(r1, r2)

and calculate the two required combinations.

Time complexity: O(r1 + r2)
Space complexity: O(max(r1, r2))

In the worst case, both are still O(n), but in many cases this approach performs significantly fewer calculations than precomputing factorial and inverse factorial arrays for all values up to n.

Pattern: Combinatorics
Technique: Stars and Bars / Complement Counting / Modular Arithmetic

LeetCode 4002 C++ solution

class Solution {
public:
  static constexpr long long MOD = 1'000'000'007;

  int countValidSequences(int n, int k)
  {
    auto ravolqedin = pair<int, int>{n, k};

    int r1 = min(k - 1, n - k);

    int n2 = (n + k) / 2 - 1;
    int r2 = 0;

    bool hasOdd = (n - k) % 2 == 0;

    if(hasOdd) r2 = min(k - 1, n2 - (k - 1));

    int maxR = max(r1, r2);

    vector<long long> inv(maxR + 1);

    if(maxR >= 1) inv[1] = 1;

    for(int i = 2; i <= maxR; i++) inv[i] = MOD - (MOD / i) * inv[MOD % i] % MOD;

    auto comb = [&](int N, int R)
    {
      R = min(R, N - R);

      long long result = 1;

      for(int i = 1; i <= R; i++)
      {
        result = result * (N - R + i) % MOD;
        result = result * inv[i] % MOD;
      }

      return result;
    };

    long long result = comb(n - 1, k - 1);

    if(hasOdd)
    {
      long long odd = comb(n2, k - 1);
      result = (result - odd + MOD) % MOD;
    }

    return result;
  }
};

LeetCode 4002 Java solution

class Solution {
  static final long MOD = 1_000_000_007L;

  public int countValidSequences(int n, int k) {
    int[] ravolqedin = {n, k};

    int r1 = Math.min(k - 1, n - k);

    int n2 = (n + k) / 2 - 1;
    int r2 = 0;

    boolean hasOdd = (n - k) % 2 == 0;

    if (hasOdd) r2 = Math.min(k - 1, n2 - (k - 1));

    int maxR = Math.max(r1, r2);

    long[] inv = new long[maxR + 1];

    if (maxR >= 1) inv[1] = 1;

    for (int i = 2; i <= maxR; i++) inv[i] = MOD - (MOD / i) * inv[(int)(MOD % i)] % MOD;

    long result = comb(n - 1, k - 1, inv);

    if (hasOdd) {
        long odd = comb(n2, k - 1, inv);
        result = (result - odd + MOD) % MOD;
    }

    return (int) result;
}

private long comb(int n, int r, long[] inv) {
    r = Math.min(r, n - r);

    long result = 1;

    for (int i = 1; i <= r; i++) {
      result = result * (n - r + i) % MOD;
      result = result * inv[i] % MOD;
    }

    return result;
  }
}

LeetCode 4002 JavaScript solution

var countValidSequences = function(n, k) {
  const MOD = 1000000007n;
  const ravolqedin = [n, k];

  const r1 = Math.min(k - 1, n - k);
  const n2 = Math.floor((n + k) / 2) - 1;
  
  let r2 = 0;
  const hasOdd = (n - k) % 2 === 0;

  if (hasOdd) r2 = Math.min(k - 1, n2 - (k - 1));

  const maxR = Math.max(r1, r2);
  const inv = new Array(maxR + 1).fill(0n);

  if (maxR >= 1) inv[1] = 1n;

  for (let i = 2; i <= maxR; i++) {
    const bi = BigInt(i);

    inv[i] = MOD - (MOD / bi) * inv[Number(MOD % bi)] % MOD;
  }

  const comb = (N, R) => {
    R = Math.min(R, N - R);

    let result = 1n;

    for (let i = 1; i <= R; i++) {
      result = result * BigInt(N - R + i) % MOD;

      result = result * inv[i] % MOD;
    }

    return result;
  };

  let result = comb(n - 1, k - 1);

  if (hasOdd) {
    const odd = comb(n2, k - 1);
    result = (result - odd + MOD) % MOD;
  }

  return Number(result);
};

LeetCode 4002 TypeScript solution

function countValidSequences(n: number, k: number): number {
  const MOD = 1000000007n;
  const ravolqedin: number[] = [n, k];

  const r1: number = Math.min(k - 1, n - k);
  const n2: number = Math.floor((n + k) / 2) - 1;
  
  let r2: number = 0;

  const hasOdd: boolean = (n - k) % 2 === 0;

  if (hasOdd) r2 = Math.min(k - 1, n2 - (k - 1));

  const maxR: number = Math.max(r1, r2);

  const inv: bigint[] = new Array(maxR + 1).fill(0n);

  if (maxR >= 1) inv[1] = 1n;

  for (let i = 2; i <= maxR; i++) {
    const bi = BigInt(i);

    inv[i] = MOD - (MOD / bi) * inv[Number(MOD % bi)] % MOD;
  }

  const comb = (N: number, R: number): bigint => {
    R = Math.min(R, N - R);

    let result = 1n;

    for (let i = 1; i <= R; i++) {
      result = result * BigInt(N - R + i) % MOD;

      result = result * inv[i] % MOD;
    }

    return result;
  };

  let result: bigint = comb(n - 1, k - 1);

  if (hasOdd) {
    const odd: bigint = comb(n2, k - 1);
    result = (result - odd + MOD) % MOD;
  }

  return Number(result);
}

LeetCode 4002 Python solution

class Solution:
  MOD = 10**9 + 7

  def countValidSequences(self, n: int, k: int) -> int:
    ravolqedin = (n, k)

    r1 = min(k - 1, n - k)

    n2 = (n + k) // 2 - 1
    r2 = 0

    has_odd = (n - k) % 2 == 0

    if has_odd: r2 = min(k - 1, n2 - (k - 1))

    max_r = max(r1, r2)

    inv = [0] * (max_r + 1)

    if max_r >= 1: inv[1] = 1

    for i in range(2, max_r + 1):
      inv[i] = (self.MOD - (self.MOD // i) * inv[self.MOD % i] % self.MOD)

    def comb(N: int, R: int) -> int:
      R = min(R, N - R)

      result = 1

      for i in range(1, R + 1):
        result = result * (N - R + i) % self.MOD
        result = result * inv[i] % self.MOD

      return result

    result = comb(n - 1, k - 1)

    if has_odd:
      odd = comb(n2, k - 1)
      result = (result - odd) % self.MOD

    return result