Combinations (nCr mod p) - Algorithm Tutorial

Binomial Coefficient (nCr mod p)

The binomial coefficient $C(n, r)$ , also written as $\binom{n}{r}$ or "n choose r", counts the number of ways to choose $r$ items from $n$ items. The formula $\frac{n!}{r!(n-r)!}$ requires modular inverse for modular arithmetic.

You precompute factorials and inverse factorials, then compute $C(n, r) = n! \cdot (r!)^{-1} \cdot ((n-r)!)^{-1} \mod p$ .

text

function precompute(maxN, mod):
    fact = array of size maxN + 1
    invFact = array of size maxN + 1

    fact[0] = 1
    for i from 1 to maxN:
        fact[i] = (fact[i-1] * i) mod mod

    invFact[maxN] = modInverse(fact[maxN], mod)
    for i from maxN - 1 down to 0:
        invFact[i] = (invFact[i+1] * (i+1)) mod mod

    return (fact, invFact)

function nCr(n, r, fact, invFact, mod):
    if r < 0 or r > n:
        return 0
    return (fact[n] * invFact[r] mod mod) * invFact[n-r] mod mod

Inverse factorial optimization: You compute $(maxN!)^{-1}$ once, then derive smaller inverse factorials: $(i!)^{-1} = ((i+1)!)^{-1} \cdot (i+1)$ .

Multiple queries: Precomputation gives you $O(1)$ per query after $O(n)$ setup.

Applications: You use binomial coefficients for probability calculations, Pascal's triangle, counting paths in grids, and combinatorial problems.

Time complexity: $O(n)$ precomputation, $O(1)$ per query.

Space complexity: $O(n)$ for factorial and inverse factorial arrays.

Combinations (nCr mod p) Algorithm Tutorial

Learn

Binomial Coefficient (nCr mod p)

Implement this Algorithm

Related Algorithms