Skip to main content
Combinatorics & Digits

Binomial Coefficients mod p

nCr = n! / (r! (n-r)!), but factorials overflow immediately and you cannot divide mod p. Precompute factorials and their modular inverses once in O(n), then every nCr query is two multiplications. Pascal's triangle is the O(n^2) alternative when n is small.

O(n) precompute, O(1) per query
·
O(n)
say this out loud

Factorials overflow and division does not work mod p, so I precompute factorials and inverse factorials once, then every query is two multiplications.

How It Works

The formula nCr = n! / (r! (n-r)!) fails twice in practice: 21! already overflows a 64-bit long, and you cannot divide under a modulus. Both are fixed by the same setup. Precompute factorials mod p in one linear pass, precompute their modular inverses, then every nCr query is fact[n] * invFact[r] * invFact[n-r], two multiplications and a modulus.

The efficient trick for the inverse table is to invert only the largest factorial with one modPow call, then walk backwards using invFact[i-1] = invFact[i] * i. That works because inverting is multiplicative, and it turns n modular inversions into exactly one. Total precompute is O(n) and each query is O(1), which is what makes problems with a million queries tractable. When n is small, under a few thousand, Pascal's triangle built with plain addition avoids modular inverses altogether and is easier to get right under time pressure.

Step-by-Step Visualization

Compute 5 choose 2 modulo a prime. The formula needs division, which modular arithmetic does not have
1
0
1
1
2
2
6
3
24
4
120
5
target5C2
1/8

Code

Java
static long[] fact, invFact;

static void build(int n) {
  fact = new long[n + 1];
  invFact = new long[n + 1];

  fact[0] = 1;
  for (int i = 1; i <= n; i++) fact[i] = fact[i - 1] * i % MOD;

  invFact[n] = modPow(fact[n], MOD - 2, MOD);   // one inversion only
  for (int i = n; i > 0; i--) invFact[i - 1] = invFact[i] * i % MOD;
}

static long nCr(int n, int r) {
  if (r < 0 || r > n) return 0;
  return fact[n] * invFact[r] % MOD * invFact[n - r] % MOD;
}

Tips & Gotchas

1Precompute factorials and inverse factorials once, then every query is two multiplications
2Build inverse factorials backwards from inv[n] so you need only one modPow call
3For small n, Pascal's triangle avoids modular inverses entirely

Practice Problems

  • 1Unique Paths
  • 2Pascal's Triangle II
  • 3Count Anagrams
  • 4Number of Ways to Reach a Position After Exactly k Steps

About the Combinatorics & Digits Pattern

Counting problems and digit problems share a habit: the naive formula overflows or the naive loop is too slow, and the fix is to reorganise the arithmetic rather than reach for a bigger integer type.

Key insight

Almost every math problem is asking you to avoid the obvious loop. Trial division to n becomes a sieve, repeated multiplication becomes binary exponentiation, and division under a modulus becomes multiplication by an inverse. If your solution loops to n or to the exponent, there is nearly always a log or sqrt version.

Common Math & Number Theory Interview Problems

  • Count Primes
  • Pow(x, n)
  • Greatest Common Divisor of Strings
  • Excel Sheet Column Title
  • Ugly Number II
  • Factorial Trailing Zeroes

Frequently Asked Questions

Why build the inverse factorials backwards?

Because invFact[i-1] equals invFact[i] * i, which follows from (i-1)! = i! / i. Starting at the top means a single modPow call for invFact[n] and then a linear walk down. Computing each inverse independently would be n calls to modPow, an O(n log m) precompute for no reason.

When should I use Pascal's triangle instead?

When n is at most a few thousand and you need many different small values. It is O(n^2) time and memory but uses only addition, so there is no modular inverse to get wrong. Above that the factorial table wins on both time and memory.

Why is Unique Paths a binomial coefficient?

A path on an m by n grid is a fixed sequence of moves: (m-1) downs and (n-1) rights in some order. Choosing which positions hold the downs determines the path, so the count is C(m+n-2, m-1). Recognising the combinatorial identity replaces an O(mn) DP with one formula.