LeetCode in Kotlin

4002. Count Valid Sequences

Medium

You are given two positive integers n and k.

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

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:

Solution

import kotlin.math.min

class Solution {
    private fun power(b: Long, e: Long): Long {
        var b = b
        var e = e
        var r: Long = 1
        while (e > 0) {
            if ((e and 1L) == 1L) {
                r = r * b % MOD
            }
            e = e shr 1
            b = b * b % MOD
        }
        return r
    }

    private fun comb(n: Int, k: Int): Long {
        var k = k
        if (k < 0 || k > n) {
            return 0
        }
        k = min(k, n - k)
        var res: Long = 1
        var den: Long = 1
        for (i in 1..k) {
            res = res * (n - i + 1) % MOD
            den = den * i % MOD
        }
        return res * power(den, MOD - 2L) % MOD
    }

    fun countValidSequences(n: Int, k: Int): Int {
        var res = comb(n - 1, k - 1)
        if (n % 2 == k % 2) {
            res = (res - comb((n + k) / 2 - 1, k - 1) + MOD) % MOD
        }
        return res.toInt()
    }

    companion object {
        private const val MOD = 1000000007
    }
}