302. Binomial Coefficient Problem

Given two integers n and k, compute the binomial coefficient C(n, k) - the number of ways to choose k items from n distinct items, without regard to order.

Input: The first line contains an integer n. The second line contains an integer k. Output: Print a single integer - the value of C(n, k).

0 <= k <= n <= 60

Updating the 1D space-optimized array from RIGHT TO LEFT (not left to right) is essential - updating left to right would use ALREADY-UPDATED values from the CURRENT row instead of the previous row's values, corrupting the recurrence.

Compute C(n,k), the number of ways to choose k items from n distinct items, order not mattering. Brute force: Compute n!/(k!*(n-k)!) directly using factorials - this works but can overflow quickly for larger n even before dividing, and requires care with large-number arithmetic; the Pascal's-triangle DP avoids ever computing a large factorial directly. Optimised: Building the table via Pascal's triangle recurrence (each entry is the sum of the two entries above it) avoids ever needing to compute or divide large factorials directly - every intermediate value stays a genuine binomial coefficient (never fractional or needing division), making it numerically cleaner for larger n.

Compute C(n, k) directly using the identity C(n, k) = product for i from 1 to k of (n - i + 1) / i, updating a single running result iteratively as result = result * (n - i + 1) / i for i = 1..k. Performing the multiplication before the division at each step guarantees the intermediate running result stays an exact integer at every step, so this needs only k multiplication/division operations and a single accumulator instead of a full triangle of stored values. Time: O(k) Space: O(1)

Build Pascal's triangle bottom-up in a 2D table where table[i][j] = table[i-1][j-1] + table[i-1][j], filling it row by row from i = 0 up to n, so every subproblem is computed exactly once from already-known smaller values. This turns the exponential recursion into simple table filling, at the cost of storing the whole triangle. Time: O(n*k) Space: O(n*k)

Compute C(n, k) by directly applying Pascal's recursive identity C(n, k) = C(n-1, k-1) + C(n-1, k), with base cases C(n, 0) = C(n, n) = 1, using plain recursion with no caching. This recomputes the same smaller (n, k) subproblems an exponential number of times as the recursion branches. Time: O(2^n) Space: O(n) recursion depth

1. C(n,k) = C(n-1,k-1) + C(n-1,k), with C(n,0)=C(n,n)=1 - build a 2D (Pascal's-triangle-style) DP table row by row. 2. You only ever need the PREVIOUS row to build the next one, so the table can be space-optimized to a single 1D array updated right to left. 3. C(n,k) is symmetric: C(n,k)==C(n,n-k), which can shrink the k you actually need to compute.

Time: O(n * k) - filling the DP table up to row n, column k. Space: O(k) with the space-optimized 1D array (updated right-to-left to avoid overwriting values still needed).

Test k = 0 and k = n (both give 1), and n = k = 60 (the upper bound, where C(n,k) can be large enough to require care with integer overflow).

Be ready to mention the symmetry property C(n,k)=C(n,n-k) as a quick optimization - computing C(n,min(k,n-k)) instead of C(n,k) directly can meaningfully reduce work when k is close to n.