Why compute nCr with the multiplicative formula instead of n!/(k!(n-k)!)?
answer
- compare the answer's size to n factorial
- 593,775 versus a 33-digit numerator
- interleave the multiplications and the divisions
- each partial result is a binomial coefficient
- multiply before dividing at every step
basics
~20 sThe factorials overflow long before the answer does. Choosing 6 winners from 30 entrants is only 593,775, yet 21! already exceeds a 64-bit signed integer. The multiplicative form interleaves multiplying and dividing, keeping every intermediate value near the answer's size.
solid answer
~40 sBecause the factorial form builds enormous numbers to produce a small one. `C(30,6)` is 593,775, but `30!` has 33 digits and even `21!` overflows a 64-bit signed integer, so the numerator is destroyed before the division ever happens. The multiplicative form computes `result = result * (n-k+i) / i` for `i` from 1 to k, multiplying *then* dividing at each step. The key invariant is that after step `i` the running value equals `C(n-k+i, i)` — itself a binomial coefficient, hence an integer — so every division is exact and no intermediate exceeds roughly `k` times the final answer. Replace `k` with `n-k` when `k` is the larger half, which halves the loop at worst. It still overflows if the answer itself is huge, and then you need arbitrary-precision or modular arithmetic.
code
pseudocode · 8 lines// C(n, k) without ever forming n!
if k > n - k:
k = n - k // symmetry: use the smaller half
result = 1
for i in 1..k:
result = result * (n - k + i) // product is divisible by i
result = result / i // exact: result == C(n-k+i, i)
return resultgo deeper
Recall that factorials explode: 21! already exceeds a 64-bit signed integer, so a formula written with n! is not a formula you can evaluate directly for anything but tiny n. Knowing the answer can be small while the numerator is not is the point.
Walk the loop step by step: why the running value is always itself a binomial coefficient, why that makes each division exact, and why swapping the multiply and the divide silently corrupts the result.
Bound the intermediates, not just the answer. Say where the loop still overflows, when to substitute n-k for k, and when the honest move is arbitrary-precision integers or arithmetic under a modulus.
Set the policy rather than the trick: one coefficient wants the O(k) loop, many reused coefficients want an additive table, and anything modular or unbounded deserves a numeric strategy written down once instead of rediscovered at each call site.
## The problem in one comparison Pick 6 winners from 30 entrants. The answer is `C(30,6) = 593,775` — a number that fits comfortably in 32 bits. The textbook formula asks you to compute it as `30! / (6! * 24!)`, and `30!` is about `2.65 x 10^32`, a 33-digit number. You are asked to build something astronomically larger than the answer, purely so it can be divided back down. On fixed-width integers that is fatal. `20!` is `2,432,902,008,176,640,000`, which just fits in a 64-bit signed integer (ceiling about `9.22 x 10^18`). `21!` is roughly `5.1 x 10^19` and does not. So the factorial form has an effective ceiling around `n = 20`, no matter how small the coefficient you actually want. Runtimes disagree about how that failure presents itself, which is worth knowing when you read someone else's code: some mainstream languages (Python, Ruby) promote integers to arbitrary precision automatically, so the naive formula merely gets slow and memory-hungry, while others (C, Java, Go) wrap silently at a fixed width and hand back a confidently wrong number with no error at all. The algorithmic fix below is the same either way, and it is the one that survives both. ## The multiplicative form Write the coefficient as a product of exactly k factors instead of a ratio of three factorials: `C(n,k) = ((n-k+1) / 1) * ((n-k+2) / 2) * ... * ((n-k+k) / k)` Evaluated left to right with a multiply immediately followed by a divide, this never leaves the integers and never builds anything enormous. ## Why every division is exact This is the part interviewers actually probe. Track what the running value *is*, not just what it holds. Before iteration `i`, the accumulated value equals `C(n-k+i-1, i-1)`. Multiply by `(n-k+i)` and divide by `i`, and by the definition of the binomial coefficient you get exactly `C(n-k+i, i)`. Since a binomial coefficient counts something, it is an integer — so the division left no remainder. Concretely for `n = 30, k = 6`: after step 1 the value is `25 = C(25,1)`; after step 2, `25 * 26 / 2 = 325 = C(26,2)`; after step 3, `325 * 27 / 3 = 2,925 = C(27,3)`; and so on up to `C(30,6) = 593,775`. Two consequences follow immediately: 1. **You must multiply before you divide.** Dividing first — `result = result / i` then multiplying — truncates, because the running value alone is generally not divisible by `i`. It is the *product* that carries the factor. One truncation early in the loop is never recovered, and the final answer is quietly wrong rather than loudly broken. 2. **The intermediates are bounded by the answer.** Every value stored between steps is `C(n-k+i, i)`, and each of those is at most `C(n,k)`. The only transient larger than the answer is the product before a division, at most `k` times the running value. So the loop's overflow threshold is roughly `k * C(n,k)`, against `n!` for the factorial form — an astronomically better bound. ## Use the smaller half Because `C(n,k) = C(n,n-k)`, replacing `k` with `n-k` whenever `k > n/2` gives the same answer with a shorter loop and the same tiny intermediates. `C(100,97)` becomes `C(100,3) = 161,700`, three iterations instead of ninety-seven. ## What the loop still cannot do The multiplicative form fixes *spurious* overflow, not *real* overflow. If the answer itself is too big for the machine word, no rearrangement saves you: `C(100,50)` is about `1.01 x 10^29`, far past 64 bits. At that point the honest options are arbitrary-precision integers, computing the value modulo something, or working with logarithms if an approximation is acceptable — and floating-point logs are an approximation, so never use them where an exact count is required. ## The alternative worth naming Repeated addition avoids division entirely: build the coefficients row by row with the additive rule `C(n,k) = C(n-1,k-1) + C(n-1,k)`. This uses no division at all, so it needs no exact-divisibility reasoning and behaves well under a modulus. It costs `O(n*k)` time and `O(n)` memory if you keep one row, versus `O(k)` time and `O(1)` memory for the multiplicative loop. Choose the loop for a single coefficient; choose the table when you need many of them, when division is unavailable, or when the whole computation is modular. ## A note on order of operations in general The deeper lesson generalises past this one formula: when a mathematically exact expression is evaluated in fixed-width or truncating arithmetic, *the order in which you apply the operations is part of the algorithm*. `a * b / c` and `a / c * b` are the same in exact arithmetic and routinely different in a machine. Knowing which arrangement keeps every intermediate integral and small is what separates a formula you can write from a formula you can run.
- Why is every division in that loop exact, with no remainder to worry about?Because after step `i` the running value equals `C(n-k+i, i)`, which counts something and is therefore an integer. The product of `i` consecutive integers always carries a factor of `i!`, so the numerator accumulated so far already contains the divisor you are about to apply. That is also why the multiply must come first: dividing first truncates, and the error never recovers.
- What is the largest value the loop holds, and can it still overflow?Stored intermediates are the coefficients `C(n-k+i, i)`, each at most the final answer, and the transient product before a division is at most `k` times that. So the loop survives inputs that kill the factorial form. But a genuinely huge answer still overflows: `C(100,50)` is about `1.01 x 10^29`. Then you need arbitrary-precision integers or a modular computation.
- When would repeated addition beat this multiplicative loop?When you need many coefficients at once, when division is unavailable, or when everything is computed under a modulus. Building rows with `C(n,k) = C(n-1,k-1) + C(n-1,k)` uses only additions, so no exact-division reasoning is needed. It costs `O(n*k)` time against the loop's `O(k)`, so it pays only when the coefficients are reused.
saying these in an interview costs you the question
- Says 64 bits is plenty for factorials
- Divides by k factorial only at the very end
- Assumes the intermediate divisions leave remainders
- Thinks a small result implies safe intermediates
- Uses floating-point factorials and trusts the digits