One Row of Pascal's Triangle
Problem
A probability library needs every binomial coefficient from C(k, 0) through C(k, k) for a given k, which is row k of Pascal's triangle counting from row 0. Given k between 0 and 1,000, return that row as a list of integers. Build it in O(k) arithmetic steps without building the rows above it.
Examples
Input: k = 3
Output: [1, 3, 3, 1]Input: k = 5
Output: [1, 5, 10, 10, 5, 1]Input: k = 0
Output: [1]
Why: edge case, row 0 holds a single 1Hints
0 / 3
Entry j of row k is C(k, j), the number of ways to choose j items out of k.
Going from C(k, j) to C(k, j + 1) changes the formula k! / (j! (k - j)!) by one factor on top and one on the bottom.
C(k, j + 1) = C(k, j) × (k - j) / (j + 1). Multiply first and then divide with //, and the division is always exact.
Solution
Each entry of row k is a binomial coefficient, and neighbouring coefficients differ by a simple ratio: C(k, j + 1) = C(k, j) × (k - j) / (j + 1). Starting from C(k, 0) = 1, each next entry costs one multiplication and one division. Multiplying before dividing keeps the arithmetic exact, because C(k, j) × (k - j) equals C(k, j + 1) × (j + 1) and so is always a multiple of j + 1, and Python's big integers mean even the middle of row 1,000 never overflows. This avoids building the k rows above, which would take O(k²) additions. The row takes O(k) arithmetic steps and O(k) space for the output.
def pascal_row(k):
row = [1]
for j in range(k):
row.append(row[-1] * (k - j) // (j + 1)) # exact: C(k, j+1) * (j+1)
return row
print(pascal_row(3)) # -> [1, 3, 3, 1]
print(pascal_row(5)) # -> [1, 5, 10, 10, 5, 1]
print(pascal_row(0)) # -> [1]Stuck on the idea rather than the code? Permutations vs Combinations covers it.