Pascal’s triangle is a pattern of the triangle which is based on nCr.below is the pictorial representation of Pascal’s triangle.
Example:
Input : N = 5
Output:
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
Approach #1:
nCr formula:
n ! / ( n – r ) ! r !
After using nCr formula, the pictorial representation becomes:
0C0
1C0 1C1
2C0 2C1 2C2
3C0 3C1 3C2 3C3
Algorithm:
- Take a number of rows to be printed, assume it to be n
- Make outer iteration i from 0 to n times to print the rows.
- Make inner iteration for j from 0 to (N – 1).
- Print single blank space ” “
- Close inner loop (j loop) //it’s needed for left spacing
- Make inner iteration for j from 0 to i.
- Print nCr of i and j.
- Close inner loop.
- Print newline character (\n) after each inner iteration.
Below is the implementation of the above approach:
Java
// Print Pascal's Triangle in Javaimport java.io.*;class GFG { public int factorial(int i) { if (i == 0) return 1; return i * factorial(i - 1); } public static void main(String[] args) { int n = 4, i, j; GFG g = new GFG(); for (i = 0; i <= n; i++) { for (j = 0; j <= n - i; j++) { // for left spacing System.out.print(" "); } for (j = 0; j <= i; j++) { // nCr formula System.out.print( " " + g.factorial(i) / (g.factorial(i - j) * g.factorial(j))); } // for newline System.out.println(); } }} |
Output
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
Time Complexity: O(N2)
Approach #2:
i’th entry in a line number line is Binomial Coefficient C(line, i) and all lines start with value 1. The idea is to calculate C(line, i) using C(line, i-1).
C(line, i) = C(line, i-1) * (line - i + 1) / i
Below is the Implementation of given approach:
Java
// Print Pascal's Triangle in Javaimport java.io.*;class GFG { // Pascal function public static void printPascal(int n) { for (int line = 1; line <= n; line++) { for (int j = 0; j <= n - line; j++) { // for left spacing System.out.print(" "); } // used to represent C(line, i) int C = 1; for (int i = 1; i <= line; i++) { // The first value in a line is always 1 System.out.print(C + " "); C = C * (line - i) / i; } System.out.println(); } } // Driver code public static void main(String[] args) { int n = 4; printPascal(n); }} |
Output
1 1 1 1 2 1 1 3 3 1
Time Complexity: O(N2)
Auxiliary space: O(1) as it is using constant space for variables
