CodingGyan

Pascal's Triangle: One Row

medium Series and Sequences

Problem

Read n and print row n of Pascal's triangle. Row 0 is 1, row 1 is 1 1, row 2 is 1 2 1, and so on. Use a method that needs only one row of memory and no other rows.

Constraints

  • 0 <= n <= 30

Examples

Input

4

Output

1 4 6 4 1

Solutions

Best approachTime O(n)Space O(1)

The numbers in row n are the binomial coefficients C(n, k). Each one is the previous one times (n - k) / (k + 1). We do not need the rows above, so only O(1) extra memory is used.

Same code works in Java810172125Basic features only, so nothing changes between versions.
/*
 * Problem : Print the n-th row of Pascal's triangle.
 * Input   : One integer n (row number, the first row is 0).
 * Output  : The numbers of row n on one line, separated by a space.
 * Approach: Each value is the previous value times (n - k) / (k + 1).
 * Time    : O(n)
 * Space   : O(1)
 * Java    : 8 or newer.
 */
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        int n = new Scanner(System.in).nextInt();
        StringBuilder line = new StringBuilder();

        // Step 1: The first number of every row is 1.
        long value = 1;

        // Step 2: Row n has n + 1 numbers. Visit position 0 to n.
        for (int position = 0; position <= n; position++) {
            // Step 3: Write the current number. Put one space between the numbers.
            if (position > 0) {
                line.append(" ");
            }
            line.append(value);

            // Step 4: Calculate the next number from this number. Example: row 4: 1 * 4 / 1 = 4, 4 * 3 / 2 = 6.
            // We multiply first and divide second. The result is always a whole number.
            value = value * (n - position) / (position + 1);
        }

        // Step 5: Print the row.
        System.out.println(line);
    }
}
Hints (2)
  1. Look at row 4: 1, 4, 6, 4, 1. How do you get 6 from 4?
  2. Multiply first, then divide, to keep whole numbers.

Try these next