Practice › Arrays
Pascal's Triangle Row
Easy · Arrays · Asked at Amazon, Microsoft, TCS, Infosys
Print the n-th row of Pascal's triangle (row 1 is 1, row 2 is 1 1, row 3 is 1 2 1).
Input
One integer n.
Output
The n values of the row, space-separated.
Constraints
- 1 ≤ n ≤ 30
Example 1
Input
5
Output
1 4 6 4 1
Example 2
Input
1
Output
1
Hints
- The values of row n are the binomial coefficients C(n-1, 0), C(n-1, 1), …
- Get each value from the previous one: C(m, k+1) = C(m, k) × (m − k) / (k + 1).
Approach
Row n holds C(n-1, k) for k = 0..n-1. Instead of building the whole triangle, compute each value from the previous one: start with 1 and multiply by (n-1-k), then divide by (k+1). Multiply before dividing so the division is always exact, and use 64-bit integers for the intermediate product.
Complexity: O(n) time · O(1) extra space
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
long long val = 1;
int m = n - 1;
for (int k = 0; k < n; k++) {
cout << val << (k + 1 < n ? " " : "\n");
val = val * (m - k) / (k + 1);
}
return 0;
}Python solution
n = int(input())
m, val, row = n - 1, 1, []
for k in range(n):
row.append(val)
val = val * (m - k) // (k + 1)
print(*row)Java solution
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt(), m = n - 1;
long val = 1;
StringBuilder sb = new StringBuilder();
for (int k = 0; k < n; k++) {
sb.append(k > 0 ? " " : "").append(val);
val = val * (m - k) / (k + 1);
}
System.out.println(sb);
}
}