Skip to main content
📜 WAYPOINT LESSON

Binomials via Factorials

⭐⭐⭐ advanced⏳ 30 min read📍 Lesson 170 of 281

C(n, r) = n! * inv(r!) * inv((n-r)!); precompute factorials and one inverse array and every query is O(1).

The factorial identity

Precompute f[i] = i! and inv[i] = (i!)^(-1); then C(n, r) is three multiplications. The inverse array builds backwards in one pass: one exponentiation total. Pascal's triangle costs O(n^2) memory and time — the difference between 1e6 and 1e12 operations.