Introduction

There is no single best way to compute nCr for every problem. The right method depends on whether you need an exact integer, a result modulo some number, or many repeated queries over a bounded range.

Start With the Requirement

Before choosing an algorithm, clarify:

• exact integer or modular result
• one query or many queries
• maximum size of n
• whether the language already provides a reliable library function

Those answers determine which implementation is actually best.

Best Practical Choice: Use the Library When Available

If your language provides a well-tested combination function, that is usually the best answer for ordinary application code.

1import math
2
3print(math.comb(5, 2))
4print(math.comb(52, 5))

Python's math.comb returns the exact binomial coefficient and handles large integers correctly. In most Python code, this is better than writing your own version.

Exact Single Query: Multiplicative Formula

If you need to implement it yourself, the multiplicative formula is usually better than raw factorials because it avoids huge intermediate values and uses the symmetry r = min(r, n-r).

1def ncr_exact(n: int, r: int) -> int:
2    if r < 0 or r > n:
3        return 0
4
5    r = min(r, n - r)
6    result = 1
7
8    for i in range(1, r + 1):
9        result = result * (n - r + i) // i
10
11    return result
12
13print(ncr_exact(5, 2))
14print(ncr_exact(52, 5))

This is a strong general-purpose algorithm for one exact query.

Why Factorials Are Often Worse

The textbook formula

n! / (r! * (n-r)!)

is mathematically correct, but directly computing three factorials is usually worse in fixed-width integer languages because the intermediate values overflow quickly.

Even in big-integer languages, it often does unnecessary work compared with the multiplicative loop.

Repeated Queries: Pascal-Style Dynamic Programming

If you need many nCr values for bounded n, precomputing Pascal's triangle can be better.

1def build_ncr(max_n: int):
2    table = [[0] * (max_n + 1) for _ in range(max_n + 1)]
3
4    for n in range(max_n + 1):
5        table[n][0] = 1
6        table[n][n] = 1
7        for r in range(1, n):
8            table[n][r] = table[n - 1][r - 1] + table[n - 1][r]
9
10    return table
11
12table = build_ncr(10)
13print(table[5][2])
14print(table[10][3])

This trades memory for fast repeated lookups.

Modular Arithmetic Needs a Different Approach

Competitive programming problems often ask for nCr mod p, usually where p is prime. In that case, the best method is often factorial precomputation plus modular inverse, not exact integer arithmetic.

1def mod_pow(base, exp, mod):
2    result = 1
3    while exp > 0:
4        if exp & 1:
5            result = (result * base) % mod
6        base = (base * base) % mod
7        exp >>= 1
8    return result
9
10def ncr_mod_prime(n, r, mod):
11    if r < 0 or r > n:
12        return 0
13
14    fact = [1] * (n + 1)
15    for i in range(1, n + 1):
16        fact[i] = fact[i - 1] * i % mod
17
18    denom = fact[r] * fact[n - r] % mod
19    return fact[n] * mod_pow(denom, mod - 2, mod) % mod
20
21print(ncr_mod_prime(5, 2, 1_000_000_007))

This is a different problem from exact integer nCr, so it deserves a different algorithm.

Use Symmetry No Matter What

A simple optimization applies to many implementations:

nCr = nC(n-r)

So always reduce r to min(r, n-r) when possible. That cuts work roughly in half for the multiplicative method and often simplifies reasoning about performance.

Common Pitfalls

The biggest pitfall is using direct factorial arithmetic in a fixed-width integer language and running into overflow long before the final answer would have fit in a bigger type.

Another issue is failing to distinguish exact arithmetic from modular arithmetic. Those are different computational problems and often require different algorithms.

Developers also ignore built-in library helpers and reimplement nCr poorly. If the standard library already gives you a correct exact answer, use it.

Finally, do not optimize for repeated queries with a large DP table unless you actually have repeated queries. For one value, that extra memory and setup is unnecessary.

Summary

• Use a trusted library helper such as math.comb when available.
• For one exact query, the multiplicative formula is usually better than direct factorials.
• For many repeated queries, Pascal-style precomputation can be worthwhile.
• For modular arithmetic, use factorials with modular inverses instead of exact integer formulas.
• Let the requirement decide the algorithm instead of looking for one universal best method.