Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

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

Example 1

Input

5

Output

1 4 6 4 1

Example 2

Input

1

Output

1

Hints

  1. The values of row n are the binomial coefficients C(n-1, 0), C(n-1, 1), …
  2. 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);
    }
}

Solve Pascal's Triangle Row online · All practice problems