Pascal’s triangle is a triangular array of the binomial coefficients. Write a function that takes an integer value n as input and prints the first n lines of Pascal’s triangle. Following are the first 6 rows of Pascal’s Triangle.In this article, we will look into the process of printing Pascal’s triangle. Pascal’s triangle is a pattern of the triangle which is based on nCr.below is the pictorial representation of Pascal’s triangle.
Illustration:
Input : N = 5
Output:
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
Methods:
There are two approaches for the same. Let’s check them out.
- Using nCr formula
- Using Binomial Coefficient
Method 1: Using nCr formula
Implementation: Follow the below algorithm for printing Pascal’s triangle using the nCr formula
- Let n be the number of rows to be printed
- Use outer iteration a from 0 to k times to print the rows
- Make inner iteration for b from 0 to (K – 1).
- Then print space as ” “.
- Close the inner ‘b’ loop.
- Make inner iteration for b from ‘0’ to ‘a’.
- Output nCr of ‘a’ and ‘b’.
- Close inner loop.
- Print newline character (\n) after each inner iteration.
Example
Java
// Java Program to Print Pascal's Triangle// Importing input output classesimport java.io.*;// Main Classpublic class GFG { // Method 1 // To find factorial of a number public int factorial(int a) { // Edge case // Factorial of 0 is unity if (a == 0) // Hence return 1 return 1; // else recursively call the function over the // number whose factorial is to be computed return a * factorial(a - 1); } // Method 2 // Main driver method public static void main(String[] args) { // Declare and initialize number whose // factorial is to be computed int k = 4; int a, b; // Creating an object of GFG class // in the main() method GFG g = new GFG(); // iterating using nested for loop to traverse over // matrix // Outer for loop for (a = 0; a <= k; a++) { // Inner loop 1 for (b = 0; b <= k - a; b++) { // Print white space for left spacing System.out.print(" "); } // Inner loop 2 for (b = 0; b <= a; b++) { // nCr formula System.out.print( " " + g.factorial(a) / (g.factorial(a - b) * g.factorial(b))); } // By now, we are done with one row so // a new line System.out.println(); } }} |
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
Time complexity: O(2n) due to recursive method
Auxiliary Space: O(n) due to recursive stack space
Method 2: Using Binomial Coefficient
The ‘A’th entry in a line number line is Binomial Coefficient C(line, a) and all lines start with value 1. The idea is to calculate C(line, a) using C(line, a-1).
C(line, i) = C(line, i-1) * (line - i + 1) / i
Implementation:
Example
Java
// Java Program to Print Pascal's Triangle// Importing input output classesimport java.io.*;// Main Classpublic class GFG { // Method 1 // Pascal function public static void printPascal(int k) { for (int line = 1; line <= k; line++) { for (int b = 0; b <= k - line; b++) { // Print whitespace for left spacing System.out.print(" "); } // Variable used to represent C(line, i) int C = 1; for (int a = 1; a <= line; a++) { // The first value in a line is always 1 System.out.print(C + " "); C = C * (line - a) / a; } // By now, we are done with one row so // a new line is required System.out.println(); } } // Method 2 // Main driver method public static void main(String[] args) { // Declare and initialize variable number // upto which Pascal's triangle is required on // console int n = 6; // Calling the Pascal function(Method 1) printPascal(n); }} |
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
Time complexity: O(n^2) where n is given input for no of rows of pascal triangle
Auxiliary Space: O(1)
