Loading…

mediumMath GeometrySometimes asked

nCr mod p

Q: How do you solve nCr mod p using the Direct Factorial Division (Baseline) approach?

When to use it: Mention first to expose the two traps — overflow and invalid modular division — that the optimal method removes. The literal translation of the formula multiplies the numerator `n!`, multiplies the denominator `r!·(n−r)!`, and divides. Adding 'mod p' to this breaks in two distinct ways. **Trap 1 — overflow without mod.** `n!` grows faster than any fixed-width integer. `21!` already overflows 64 bits, so for any interesting `n` the numerator is garbage long before you divide. Big integers avoid the overflow but make every query slow and miss the point of working mod p. **Trap 2 — division is not modular.** Suppose you reduce numerator and denominator mod p to keep them small. Now you're stuck: `(a / b) mod p` is **not** `(a mod p) / (b mod p)`. Concretely, `(10 / 2) mod 7 = 5`, but `(10 mod 7) / (2 mod 7) = 3 / 2`, which isn't even an integer. Modular arithmetic has no native division; you can only multiply. So a mod-as-you-go factorial leaves you unable to perform the final divide. **The fix the optimal uses.** Division by `b` modulo `p` must become multiplication by `b⁻¹`, the modular inverse of `b`. Since `p` is prime, that inverse exists for every `b` not divisible by `p` and is given by Fermat's little theorem. That single substitution — divide becomes multiply-by-inverse — is what makes the whole computation valid mod p. Time complexity: O(n) per query. Space complexity: O(1).

Math & Number Theory · 27 of 36 · 12 min

Given integers n, r, and a prime modulus p with p > n, compute the binomial coefficient

C(n, r) = n! / (r! · (n − r)!) taken modulo p.

You will answer many such queries against the same p (commonly p = 1\,000\,000\,007). Preprocess once so each query is O(1). Define C(n, r) = 0 when r < 0 or r > n.

In plain English

C(n, r) counts subsets of size r from n items, but we want it modulo a prime p, not exactly. Two obstacles: n! is astronomically large (overflow), and the formula divides — and division is not a native modular operation. We fix both at once. Work in arithmetic mod p so numbers stay small, and replace each division by multiplication with a modular inverse. Because p is prime, Fermat's little theorem gives the inverse as a power, and one clever backward pass produces every inverse-factorial cheaply.

Examples

Example 1

Input: n = 5, r = 2, p = 1000000007
Output: 10
Note: C(5,2) = 10, and 10 < p so the answer is just 10. fact[5]=120, invFact[2]·invFact[3] reconstruct 120/(2·6)=10.

Example 2

Input: n = 10, r = 3, p = 13
Output: 3
Note: C(10,3) = 120, and 120 mod 13 = 3. Note p = 13 > n = 10, so Fermat applies.

Example 3

Input: n = 4, r = 5, p = 1000000007
Output: 0
Note: r > n, so C(4,5) = 0 by definition — guarded before any table lookup.

Constraints

0 ≤ r ≤ n ≤ 10⁶ (precompute factorial tables of this size)
p is prime and p > n (so Fermat's inverse applies and no factor of p appears in n!)
p ≤ 10⁹ + 7 (typical), products fit in 64-bit after each mod
Many queries → O(n) precompute, O(1) per query is required
Return 0 for r < 0 or r > n

Clarifying questions4First question: Is p prime, and is p larger than n?Explore questions

Q1.Is p prime, and is p larger than n?
Yes on both — that's the regime where Fermat's inverse works and no factor of p divides into n!. If n could exceed p, I'd switch to Lucas' theorem.
Q2.How many queries, and what's the max n?
Many queries (that's why we precompute), with n up to ~10⁶. So O(n) setup and O(1) per query, not O(log p) per query.
Q3.What should C(n, r) be when r is out of range?
0 for r < 0 or r > n. I guard that first so I never index a factorial table with a negative or oversized index.
Q4.What modulus should I assume?
Usually 1e9+7, which is prime. The method works for any prime p > n; I'll keep p as a parameter.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

You can't compute n! / (r!·(n−r)!) then take mod p, because the division isn't valid in modular arithmetic and n! overflows. The fix when p is prime and p > n: precompute factorials fact[0..n] mod p and their modular inverses, then nCr mod p = fact[n] · invFact[r] · invFact[n−r] mod p. The inverse comes from Fermat's little theorem: a⁻¹ ≡ a^(p−2) (mod p). Precompute in O(n) (one pass for factorials, one inverse via Fermat, then a backward pass), and answer each query in O(1).

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you know that modular division must go through a modular inverse, that Fermat's little theorem supplies that inverse when p is prime, and that all inverse-factorials can be derived from a single modpow in O(n).

Where candidates slip

Computing n!/(r!(n−r)!) with integer division before taking mod (wrong and overflowing), or calling modpow once per query (turning O(1) answers into O(log p) each, and the precompute into O(n log p)).

How to stand out

Derive the inverse from Fermat out loud (a^(p−1) ≡ 1 ⇒ a⁻¹ ≡ a^(p−2)), and show the backward sweep invFact[i] = invFact[i+1]·(i+1) that needs only one modpow for the whole table.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Direct Factorial Division (Baseline)	`O(n) per query`	`O(1)`	Mention first to expose the two traps — overflow and invalid modular division — that the optimal method removes.	Read
2	Precomputed Factorials + Fermat Inverse (Optimal)Optimal	`O(n + log p) precompute, O(1) per query`	`O(n)`	The answer they want. Lead with 'division becomes multiply-by-inverse, and Fermat gives the inverse since p is prime'.	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.First decision previewfact[i] = fact[i-1]*i % p (forward, O(n))query (n, r)r<0 or r>nvalidExplore the full tree

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Direct Factorial Division (Baseline)

TimeO(n) per querySpaceO(1)

Mention first to expose the two traps — overflow and invalid modular division — that the optimal method removes.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

The textbook formula is n! / (r! (n−r)!). The most direct code multiplies out the factorials and divides. What two things go wrong when we add 'mod p'?

2Hint 2Explore hint

n! overflows fast — 21! already exceeds a 64-bit integer. And taking mod of a quotient is not the quotient of the mods: (a / b) mod p ≠ (a mod p) / (b mod p).

3Hint 3Explore hint

Even computing the factorials mod p doesn't save you, because once you've reduced numerator and denominator mod p you can no longer divide them — division isn't defined in modular arithmetic without an inverse.

A · Core idea

The literal translation of the formula multiplies the numerator n!, multiplies the denominator r!·(n−r)!, and divides. Adding 'mod p' to this breaks in two distinct ways.

Trap 1 — overflow without mod. n! grows faster than any fixed-width integer. 21! already overflows 64 bits, so for any interesting n the numerator is garbage long before you divide. Big integers avoid the overflow but make every query slow and miss the point of working mod p.

Trap 2 — division is not modular. Suppose you reduce numerator and denominator mod p to keep them small. Now you're stuck: (a / b) mod p is not (a mod p) / (b mod p). Concretely, (10 / 2) mod 7 = 5, but (10 mod 7) / (2 mod 7) = 3 / 2, which isn't even an integer. Modular arithmetic has no native division; you can only multiply. So a mod-as-you-go factorial leaves you unable to perform the final divide.

The fix the optimal uses. Division by b modulo p must become multiplication by b⁻¹, the modular inverse of b. Since p is prime, that inverse exists for every b not divisible by p and is given by Fermat's little theorem. That single substitution — divide becomes multiply-by-inverse — is what makes the whole computation valid mod p.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

n = 5, r = 2, p = 1000000007

numerator

5! = 120 → 120 mod p = 120

Stateok so far

Final result10 here, but the method is unsound in general

C · Code with teaching comments

Reference implementation preview// Unsound under mod for general inputs; shown to illustrate the trap. public long nCrNaive(int n, int r) { if (r < 0 || r > n) return 0; long num = 1, den = 1; for (int i = 0; i < r; i++) {Explore the full code

solution.javaJava

Direct Factorial Division (Baseline) — reference

2 teaching notes

1
// Unsound under mod for general inputs; shown to illustrate the trap.
2
public long nCrNaive(int n, int r) {
3
    if (r < 0 || r > n) return 0;
4
    long num = 1, den = 1;
5
    for (int i = 0; i < r; i++) {
6
        num *= (n - i);   // overflows quickly for large n
7
        den *= (i + 1);
8
    }
9
    return num / den;     // plain division — cannot be made modular
10
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.10 lines

D · Why it works and complexityO(n) per query timeO(1) spaceOpen the invariant and proofExplore the proof

The baseline fails not because it's slow but because it's wrong under a modulus: you cannot divide in modular arithmetic. The entire optimal method is one idea — replace ÷b with ×b⁻¹ — plus precomputation so each inverse is cheap.

ComplexityO(n) per query time, O(1) space — Multiplying n factors for the factorials is O(n) per query, with O(1) extra space. But the real problem is correctness: without modular inverses you either overflow (no mod) or compute a meaningless quotient (mod then divide).

E · Edge cases and pitfalls3Reducing mod p and then dividing — division isn't defined modulo p.Explore edge cases

Pitfalls

Reducing mod p and then dividing — division isn't defined modulo p.
Letting n! overflow a fixed-width integer.
Recomputing factorials from scratch per query — O(n) each instead of O(1).

03.2

Approach 2 of 2 · Optimal

Precomputed Factorials + Fermat Inverse (Optimal)

TimeO(n + log p) precompute, O(1) per querySpaceO(n)

The answer they want. Lead with 'division becomes multiply-by-inverse, and Fermat gives the inverse since p is prime'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

C(n, r) = fact[n] · (fact[r])⁻¹ · (fact[n−r])⁻¹ mod p. The only hard part is the inverse — what does Fermat's little theorem say about a⁻¹ when p is prime?

2Hint 2Explore hint

Fermat: a^(p−1) ≡ 1 (mod p) for a not divisible by p, so a⁻¹ ≡ a^(p−2) (mod p) via fast modular exponentiation.

3Hint 3Explore hint

You don't need n separate modpow calls. Invert fact[n] once, then invFact[i] = invFact[i+1]·(i+1) mod p going backward — because (i!)⁻¹ = ((i+1)!)⁻¹ · (i+1).

A · Core idea

Work entirely in arithmetic modulo p and replace the single division in the binomial formula with multiplication by modular inverses.

The formula in modular form. C(n, r) = fact[n] · invFact[r] · invFact[n−r] (mod p), where fact[i] = i! mod p and invFact[i] = (i!)⁻¹ mod p. Every value stays in [0, p), so nothing overflows once we reduce after each multiply.

Why Fermat gives the inverse. p is prime, and any a with 1 ≤ a < p satisfies gcd(a, p) = 1. Fermat's little theorem then says a^(p−1) ≡ 1 (mod p). Multiply both sides by a⁻¹: a^(p−2) ≡ a⁻¹ (mod p). So the inverse of any factorial is just that factorial raised to the p−2 power, computed with fast modular exponentiation in O(log p). (This needs p > n so that no i ≤ n is a multiple of p — otherwise fact[i] would be 0 mod p and have no inverse.)

Why one modpow is enough for all inverses. Calling a^(p−2) for every factorial would be O(n log p) — wasteful. Instead invert only the top: invFact[n] = fact[n]^(p−2) mod p. Then use the relation (i!)⁻¹ = ((i+1)!)⁻¹ · (i+1) (since (i+1)! = (i+1)·i!, inverting both sides gives this). Sweeping i from n−1 down to 0 fills the whole invFact table with one multiplication each — a single modpow for the entire array.

Why each query is O(1). After the tables exist, a query is fact[n] · invFact[r] mod p · invFact[n−r] mod p — two multiplications and a couple of mods. Guard r < 0 || r > n first and return 0, both because the coefficient is genuinely 0 there and because invFact[n−r] with a negative index would crash.

Why overflow-safe. Each product of two values < p (with p ≈ 10⁹) is up to ~10¹⁸, which fits in a signed 64-bit long — but only if you take mod p after every multiplication so it never compounds. Python integers are unbounded, so the mod is for speed and to match the math, not to prevent overflow.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

n = 5, r = 2, p = 13

Array state

fact ready

factorials mod 13

[0]

[1]

[2]

[3]

[4]

i ↓

[5]

Current pointerResolved stateNot processed

Final resultC(5,2) mod 13 = 10 (C(5,2) = 10, and 10 < 13)

C · Code with teaching comments

solution.javaJava

Precomputed Factorials + Fermat Inverse (Optimal) — optimal

5 teaching notes

1
import java.util.*;
2
 
3
class Binomial {
4
    private final long p;
5
    private final long[] fact, invFact;
6
 
7
    Binomial(int maxN, long p) {
8
        this.p = p;
9
        fact = new long[maxN + 1];
10
        invFact = new long[maxN + 1];
11
        fact[0] = 1;
12
        for (int i = 1; i <= maxN; i++) {
13
            fact[i] = fact[i - 1] * i % p;     // forward, mod after each multiply
14
        }
15
        invFact[maxN] = modpow(fact[maxN], p - 2, p); // one Fermat inverse
16
        for (int i = maxN - 1; i >= 0; i--) {
17
            invFact[i] = invFact[i + 1] * (i + 1) % p; // backward sweep
18
        }
19
    }
20
 
21
    long nCr(int n, int r) {
22
        // Guards the out-of-range definition and prevents indexing invFact[n−r] with a
23
        // negative index.
24
        if (r < 0 || r > n) return 0;
25
        // The modular binomial: divide became multiply-by-inverse. Mod between the two
26
        // products keeps everything < p².
27
        return fact[n] * invFact[r] % p * invFact[n - r] % p;
28
    }
29
 
30
    private long modpow(long base, long exp, long mod) {
31
        long result = 1 % mod;
32
        base %= mod;
33
        while (exp > 0) {
34
            if ((exp & 1) == 1) result = result * base % mod;
35
            base = base * base % mod;
36
            exp >>= 1;
37
        }
38
        return result;
39
    }
40
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.40 lines

D · Why it works and complexityO(n + log p) precompute, O(1) per query timeO(n) spaceOpen the invariant and proofExplore the proof

The whole method is the substitution 'divide by b' → 'multiply by b^(p−2)', made cheap by precomputation. The elegant trick is deriving the entire inverse-factorial table from a single modpow via the backward recurrence — turning what looks like n exponentiations into n multiplications. Remember the precondition p > n and prime; the moment n can exceed p, Fermat's indexing breaks and Lucas' theorem takes over.

ComplexityO(n + log p) precompute, O(1) per query time, O(n) space — Building fact[0..n] is O(n) multiplications. One Fermat inverse via fast exponentiation is O(log p). The backward sweep for invFact is another O(n). So precompute is O(n + log p); every query is three O(1) array lookups and two multiplications.

E · Edge cases and pitfalls9nCr(n, 0) or nCr(n, n) — invFact[0] = 1, so both equal fact[n]·1·invFact[n] = 1, the correct value.Explore edge cases

Edge cases handled

nCr(n, 0) or nCr(n, n)invFact[0] = 1, so both equal fact[n]·1·invFact[n] = 1, the correct value.
nCr(0, 0)fact[0]·invFact[0]·invFact[0] = 1·1·1 = 1.
r > nGuard returns 0 before any lookup.
n close to pFine as long as n < p; if n ≥ p, fact has a 0 factor and the method is invalid — use Lucas.

Pitfalls

Calling modpow once per factorial inverse — O(n log p); the backward sweep needs only one modpow.
Forgetting mod after a multiply — the long overflows or Python slows on huge ints.
Skipping the r < 0 / r > n guard — wrong value and a negative index into invFact.
Using Fermat when p is not prime, or when n ≥ p — both break; use Lucas or extended-GCD inverses.
Using int in Java for fact/invFact products — overflow; everything must be long.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewimport java.util.*; class Binomial { private final long p; private final long[] fact, invFact;Explore the playground

Try it — Java· run a complete program; method snippets need a driver

import java.util.*;

class Binomial {
    private final long p;
    private final long[] fact, invFact;

Binomial(int maxN, long p) {
        this.p = p;
        fact = new long[maxN + 1];
        invFact = new long[maxN + 1];
        fact[0] = 1;
        for (int i = 1; i <= maxN; i++) {
            fact[i] = fact[i - 1] * i % p;     // forward, mod after each multiply
        }
        invFact[maxN] = modpow(fact[maxN], p - 2, p); // one Fermat inverse
        for (int i = maxN - 1; i >= 0; i--) {
            invFact[i] = invFact[i + 1] * (i + 1) % p; // backward sweep
        }
    }

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

private long modpow(long base, long exp, long mod) {
        long result = 1 % mod;
        base %= mod;
        while (exp > 0) {
            if ((exp & 1) == 1) result = result * base % mod;
            base = base * base % mod;
            exp >>= 1;
        }
        return result;
    }
}

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Dividing instead of multiplying by the inverse

Modular arithmetic has no division. (a / b) mod p is not (a mod p) / (b mod p); the correct operation is a · b⁻¹ mod p, where b⁻¹ comes from Fermat.

Explore the code comparison

Don't write this

long num = fact[n];
long den = fact[r] * fact[n - r] % p;
return num / den % p;        // WRONG: integer division under a modulus

Write this instead

return fact[n] * invFact[r] % p * invFact[n - r] % p; // multiply by inverses

One modpow per factorial inverse

Inverting every factorial separately is O(n log p). Inverting only fact[n] and sweeping backward with (i!)⁻¹ = ((i+1)!)⁻¹·(i+1) costs one modpow plus O(n) multiplies.

Explore the code comparison

Don't write this

inv_fact = [pow(self.fact[i], p - 2, p) for i in range(max_n + 1)]  # O(n log p)

Write this instead

inv_fact = [1] * (max_n + 1)
inv_fact[max_n] = pow(self.fact[max_n], p - 2, p)
for i in range(max_n - 1, -1, -1):
    inv_fact[i] = inv_fact[i + 1] * (i + 1) % p

Missing mod after a multiply (overflow)

fact[i-1] * i without an immediate % p compounds across iterations and overflows a 64-bit long quickly; the table fills with garbage.

Explore the code comparison

Don't write this

fact[i] = fact[i - 1] * i;        // no mod — overflows long

Write this instead

fact[i] = fact[i - 1] * i % p;    // reduce after every multiply

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Precomputed factorials + modular inverse via Fermat's little theorem

Code pattern to memorize

fact[0]=1; fact[i]=fact[i-1]*i % p
invFact[n]=modpow(fact[n], p-2, p)        # Fermat
for i from n-1 down to 0: invFact[i]=invFact[i+1]*(i+1) % p
nCr = fact[n] * invFact[r] % p * invFact[n-r] % p

Rules to remember

1Never compute n!/(r!(n−r)!) with integer division then mod — division isn't modular; multiply by the modular inverse instead.
2Fermat's little theorem needs p prime and gcd(a, p) = 1: then a^(p−1) ≡ 1, so a⁻¹ ≡ a^(p−2) (mod p).
3Compute all inverse-factorials with one modpow: invert fact[n] once, then walk backward invFact[i] = invFact[i+1]·(i+1). Don't run modpow n times.
4Return 0 immediately if r < 0 or r > n — nCr is 0 there, and indexing invFact[n−r] with a negative index is a bug.
5Take mod after every multiplication and use long in Java — fact[i-1]*i and the triple product exceed 32 bits well before n is large.

Use this pattern when

Many binomial-coefficient queries nCr mod p with a fixed prime modulus (often 1e9+7)
n is up to ~10⁶–10⁷ and p is prime with p > n
Counting problems (paths, sequences, distributions) reduced to binomials under a prime mod
You need O(1) per query after an O(n) precompute

Choose another pattern when

n is larger than p (or p is small) → Fermat indexing breaks; use **Lucas' theorem** instead
The modulus is **not prime** → Fermat doesn't apply; use extended GCD inverses or CRT over prime-power factors
You need exact (non-modular) huge binomials → big integers, Pascal's triangle, no inverse trick
Only a single small nCr is needed → multiplicative formula with divide-as-you-go is enough

Interview takeaway

Binomials under a prime mod are a two-line idea once you accept that 'division' becomes 'multiply by the modular inverse'. Precompute factorials forward, invert the top factorial once with Fermat, then sweep inverses backward — O(n) setup, O(1) queries. The trap is reaching for integer division; the fix is Fermat's a^(p−2). When n exceeds p, this breaks and Lucas takes over.

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Transferable patternPrecomputed factorials with modular inverse. The default for many binomial queries under a fixed prime mod. Recognise it whenever a counting answer reduces to nCr mod p with p prime and p > n; the same fact/invFact tables power Catalan numbers, stars-and-bars counts, and inclusion–exclusion sums mod p.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Same pattern

←

Matrix Exponentiation (Fibonacci)

Continue · Next problem

Nth Fibonacci Number

mediumMath GeometrySometimes asked

nCr mod p

Math & Number Theory · 27 of 36 · 12 min

Given integers n, r, and a prime modulus p with p > n, compute the binomial coefficient

C(n, r) = n! / (r! · (n − r)!) taken modulo p.

You will answer many such queries against the same p (commonly p = 1\,000\,000\,007). Preprocess once so each query is O(1). Define C(n, r) = 0 when r < 0 or r > n.

In plain English

Examples

Example 1

Input: n = 5, r = 2, p = 1000000007
Output: 10
Note: C(5,2) = 10, and 10 < p so the answer is just 10. fact[5]=120, invFact[2]·invFact[3] reconstruct 120/(2·6)=10.

Example 2

Input: n = 10, r = 3, p = 13
Output: 3
Note: C(10,3) = 120, and 120 mod 13 = 3. Note p = 13 > n = 10, so Fermat applies.

Example 3

Input: n = 4, r = 5, p = 1000000007
Output: 0
Note: r > n, so C(4,5) = 0 by definition — guarded before any table lookup.

Constraints

0 ≤ r ≤ n ≤ 10⁶ (precompute factorial tables of this size)
p is prime and p > n (so Fermat's inverse applies and no factor of p appears in n!)
p ≤ 10⁹ + 7 (typical), products fit in 64-bit after each mod
Many queries → O(n) precompute, O(1) per query is required
Return 0 for r < 0 or r > n

Clarifying questions4First question: Is p prime, and is p larger than n?Explore questions

Q1.Is p prime, and is p larger than n?
Yes on both — that's the regime where Fermat's inverse works and no factor of p divides into n!. If n could exceed p, I'd switch to Lucas' theorem.
Q2.How many queries, and what's the max n?
Many queries (that's why we precompute), with n up to ~10⁶. So O(n) setup and O(1) per query, not O(log p) per query.
Q3.What should C(n, r) be when r is out of range?
0 for r < 0 or r > n. I guard that first so I never index a factorial table with a negative or oversized index.
Q4.What modulus should I assume?
Usually 1e9+7, which is prime. The method works for any prime p > n; I'll keep p as a parameter.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Where candidates slip

How to stand out

Derive the inverse from Fermat out loud (a^(p−1) ≡ 1 ⇒ a⁻¹ ≡ a^(p−2)), and show the backward sweep invFact[i] = invFact[i+1]·(i+1) that needs only one modpow for the whole table.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Direct Factorial Division (Baseline)	`O(n) per query`	`O(1)`	Mention first to expose the two traps — overflow and invalid modular division — that the optimal method removes.	Read
2	Precomputed Factorials + Fermat Inverse (Optimal)Optimal	`O(n + log p) precompute, O(1) per query`	`O(n)`	The answer they want. Lead with 'division becomes multiply-by-inverse, and Fermat gives the inverse since p is prime'.	Read

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Direct Factorial Division (Baseline)

TimeO(n) per querySpaceO(1)

Mention first to expose the two traps — overflow and invalid modular division — that the optimal method removes.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

The textbook formula is n! / (r! (n−r)!). The most direct code multiplies out the factorials and divides. What two things go wrong when we add 'mod p'?

2Hint 2Explore hint

n! overflows fast — 21! already exceeds a 64-bit integer. And taking mod of a quotient is not the quotient of the mods: (a / b) mod p ≠ (a mod p) / (b mod p).

3Hint 3Explore hint

A · Core idea

The literal translation of the formula multiplies the numerator n!, multiplies the denominator r!·(n−r)!, and divides. Adding 'mod p' to this breaks in two distinct ways.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

n = 5, r = 2, p = 1000000007

numerator

5! = 120 → 120 mod p = 120

Stateok so far

Final result10 here, but the method is unsound in general

C · Code with teaching comments

solution.javaJava

Direct Factorial Division (Baseline) — reference

2 teaching notes

1
// Unsound under mod for general inputs; shown to illustrate the trap.
2
public long nCrNaive(int n, int r) {
3
    if (r < 0 || r > n) return 0;
4
    long num = 1, den = 1;
5
    for (int i = 0; i < r; i++) {
6
        num *= (n - i);   // overflows quickly for large n
7
        den *= (i + 1);
8
    }
9
    return num / den;     // plain division — cannot be made modular
10
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.10 lines

D · Why it works and complexityO(n) per query timeO(1) spaceOpen the invariant and proofExplore the proof

E · Edge cases and pitfalls3Reducing mod p and then dividing — division isn't defined modulo p.Explore edge cases

Pitfalls

Reducing mod p and then dividing — division isn't defined modulo p.
Letting n! overflow a fixed-width integer.
Recomputing factorials from scratch per query — O(n) each instead of O(1).

03.2

Approach 2 of 2 · Optimal

Precomputed Factorials + Fermat Inverse (Optimal)

TimeO(n + log p) precompute, O(1) per querySpaceO(n)

The answer they want. Lead with 'division becomes multiply-by-inverse, and Fermat gives the inverse since p is prime'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

C(n, r) = fact[n] · (fact[r])⁻¹ · (fact[n−r])⁻¹ mod p. The only hard part is the inverse — what does Fermat's little theorem say about a⁻¹ when p is prime?

2Hint 2Explore hint

Fermat: a^(p−1) ≡ 1 (mod p) for a not divisible by p, so a⁻¹ ≡ a^(p−2) (mod p) via fast modular exponentiation.

3Hint 3Explore hint

You don't need n separate modpow calls. Invert fact[n] once, then invFact[i] = invFact[i+1]·(i+1) mod p going backward — because (i!)⁻¹ = ((i+1)!)⁻¹ · (i+1).

A · Core idea

Work entirely in arithmetic modulo p and replace the single division in the binomial formula with multiplication by modular inverses.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

n = 5, r = 2, p = 13

Array state

fact ready

factorials mod 13

[0]

[1]

[2]

[3]

[4]

i ↓

[5]

Current pointerResolved stateNot processed

Final resultC(5,2) mod 13 = 10 (C(5,2) = 10, and 10 < 13)

C · Code with teaching comments

solution.javaJava

Precomputed Factorials + Fermat Inverse (Optimal) — optimal

5 teaching notes

1
import java.util.*;
2
 
3
class Binomial {
4
    private final long p;
5
    private final long[] fact, invFact;
6
 
7
    Binomial(int maxN, long p) {
8
        this.p = p;
9
        fact = new long[maxN + 1];
10
        invFact = new long[maxN + 1];
11
        fact[0] = 1;
12
        for (int i = 1; i <= maxN; i++) {
13
            fact[i] = fact[i - 1] * i % p;     // forward, mod after each multiply
14
        }
15
        invFact[maxN] = modpow(fact[maxN], p - 2, p); // one Fermat inverse
16
        for (int i = maxN - 1; i >= 0; i--) {
17
            invFact[i] = invFact[i + 1] * (i + 1) % p; // backward sweep
18
        }
19
    }
20
 
21
    long nCr(int n, int r) {
22
        // Guards the out-of-range definition and prevents indexing invFact[n−r] with a
23
        // negative index.
24
        if (r < 0 || r > n) return 0;
25
        // The modular binomial: divide became multiply-by-inverse. Mod between the two
26
        // products keeps everything < p².
27
        return fact[n] * invFact[r] % p * invFact[n - r] % p;
28
    }
29
 
30
    private long modpow(long base, long exp, long mod) {
31
        long result = 1 % mod;
32
        base %= mod;
33
        while (exp > 0) {
34
            if ((exp & 1) == 1) result = result * base % mod;
35
            base = base * base % mod;
36
            exp >>= 1;
37
        }
38
        return result;
39
    }
40
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.40 lines

D · Why it works and complexityO(n + log p) precompute, O(1) per query timeO(n) spaceOpen the invariant and proofExplore the proof

E · Edge cases and pitfalls9nCr(n, 0) or nCr(n, n) — invFact[0] = 1, so both equal fact[n]·1·invFact[n] = 1, the correct value.Explore edge cases

Edge cases handled

nCr(n, 0) or nCr(n, n)invFact[0] = 1, so both equal fact[n]·1·invFact[n] = 1, the correct value.
nCr(0, 0)fact[0]·invFact[0]·invFact[0] = 1·1·1 = 1.
r > nGuard returns 0 before any lookup.
n close to pFine as long as n < p; if n ≥ p, fact has a 0 factor and the method is invalid — use Lucas.

Pitfalls

Calling modpow once per factorial inverse — O(n log p); the backward sweep needs only one modpow.
Forgetting mod after a multiply — the long overflows or Python slows on huge ints.
Skipping the r < 0 / r > n guard — wrong value and a negative index into invFact.
Using Fermat when p is not prime, or when n ≥ p — both break; use Lucas or extended-GCD inverses.
Using int in Java for fact/invFact products — overflow; everything must be long.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewimport java.util.*; class Binomial { private final long p; private final long[] fact, invFact;Explore the playground

Try it — Java· run a complete program; method snippets need a driver

import java.util.*;

class Binomial {
    private final long p;
    private final long[] fact, invFact;

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

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Dividing instead of multiplying by the inverse

Modular arithmetic has no division. (a / b) mod p is not (a mod p) / (b mod p); the correct operation is a · b⁻¹ mod p, where b⁻¹ comes from Fermat.

Explore the code comparison

Don't write this

long num = fact[n];
long den = fact[r] * fact[n - r] % p;
return num / den % p;        // WRONG: integer division under a modulus

Write this instead

return fact[n] * invFact[r] % p * invFact[n - r] % p; // multiply by inverses

One modpow per factorial inverse

Inverting every factorial separately is O(n log p). Inverting only fact[n] and sweeping backward with (i!)⁻¹ = ((i+1)!)⁻¹·(i+1) costs one modpow plus O(n) multiplies.

Explore the code comparison

Don't write this

inv_fact = [pow(self.fact[i], p - 2, p) for i in range(max_n + 1)]  # O(n log p)

Write this instead

inv_fact = [1] * (max_n + 1)
inv_fact[max_n] = pow(self.fact[max_n], p - 2, p)
for i in range(max_n - 1, -1, -1):
    inv_fact[i] = inv_fact[i + 1] * (i + 1) % p

Missing mod after a multiply (overflow)

fact[i-1] * i without an immediate % p compounds across iterations and overflows a 64-bit long quickly; the table fills with garbage.

Explore the code comparison

Don't write this

fact[i] = fact[i - 1] * i;        // no mod — overflows long

Write this instead

fact[i] = fact[i - 1] * i % p;    // reduce after every multiply

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Precomputed factorials + modular inverse via Fermat's little theorem

Code pattern to memorize

fact[0]=1; fact[i]=fact[i-1]*i % p
invFact[n]=modpow(fact[n], p-2, p)        # Fermat
for i from n-1 down to 0: invFact[i]=invFact[i+1]*(i+1) % p
nCr = fact[n] * invFact[r] % p * invFact[n-r] % p

Rules to remember

1Never compute n!/(r!(n−r)!) with integer division then mod — division isn't modular; multiply by the modular inverse instead.
2Fermat's little theorem needs p prime and gcd(a, p) = 1: then a^(p−1) ≡ 1, so a⁻¹ ≡ a^(p−2) (mod p).
3Compute all inverse-factorials with one modpow: invert fact[n] once, then walk backward invFact[i] = invFact[i+1]·(i+1). Don't run modpow n times.
4Return 0 immediately if r < 0 or r > n — nCr is 0 there, and indexing invFact[n−r] with a negative index is a bug.
5Take mod after every multiplication and use long in Java — fact[i-1]*i and the triple product exceed 32 bits well before n is large.

Use this pattern when

Many binomial-coefficient queries nCr mod p with a fixed prime modulus (often 1e9+7)
n is up to ~10⁶–10⁷ and p is prime with p > n
Counting problems (paths, sequences, distributions) reduced to binomials under a prime mod
You need O(1) per query after an O(n) precompute

Choose another pattern when

n is larger than p (or p is small) → Fermat indexing breaks; use **Lucas' theorem** instead
The modulus is **not prime** → Fermat doesn't apply; use extended GCD inverses or CRT over prime-power factors
You need exact (non-modular) huge binomials → big integers, Pascal's triangle, no inverse trick
Only a single small nCr is needed → multiplicative formula with divide-as-you-go is enough

Interview takeaway

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Same pattern

←

Matrix Exponentiation (Fibonacci)

Continue · Next problem

Nth Fibonacci Number