1. Out of range
Choosing fewer than 0 or more than n items is impossible, so the count is 0.
if (r < 0 || r > n) return 0Typorithm · medium
Combinations nCr
▷ Interactive algorithm labcombinations-ncrmathcombinatoricsmultiplicativeoverflow
Saved on this device
Full lesson · 8 learning steps Open any exercise for focused practice
10%
Step 1 of 8 · intro card
Learn Combinations nCr
Math & Number Theory
Build C(n, r) iteratively: multiply by (n - i) and divide by (i + 1) for r steps, staying integer throughout.
C(n, r) counts the ways to choose r items from n, equal to n! / (r! * (n-r)!).
Computing factorials directly overflows, so the multiplicative form interleaves a multiply and a divide each step.
Multiplying by (n - i) before dividing by (i + 1) keeps the running result an exact integer; using min(r, n-r) cuts the loop count.
Preparing algorithm lab…
01
Loop r = min(r, n-r) times.
02
Multiply by (n - i), divide by (i + 1).
03
Each partial product is exact.
function nCr(n, r) {
if (r < 0 || r > n) return 0;
if (r > n - r) r = n - r;
let result = 1;
for (let i = 0; i < r; i += 1) {
result = (result * (n - i)) / (i + 1);
}
return result;
}Read the implementation
Connect each part of the code to the concept before you type.
2. Use smaller r
C(n, r) = C(n, n-r), so loop the smaller of r and n-r for fewer iterations.
if (r > n - r) r = n - r3. Multiplicative step
Multiply by the next numerator (n-i) then divide by (i+1); the running product stays an exact integer.
result = (result * (n - i)) / (i + 1)4. r iterations
The product needs exactly r factor pairs to build C(n, r).
for (let i = 0; i < r; i += 1)A complete learning loop
01
Understand
Read the concept map and follow the code breakdown.
02
Reconstruct
Type the implementation, repair mistakes and work through every recall exercise.
03
Verify
Use the final check without hints; revisit weak concepts in short practice sessions.