Pascal’s triangle is a triangular array of the binomial coefficients. Write a function that takes an integer value n as input and prints first n lines of the Pascal’s triangle. Following are the first 6 rows of Pascal’s Triangle.
1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1
We strongly recommend that you click here and practice it, before moving on to the solution.
Method 1 ( O(n^3) time complexity )
Number of entries in every line is equal to line number. For example, the first line has “1”, the second line has “1 1”, the third line has “1 2 1”,.. and so on. Every entry in a line is value of a Binomial Coefficient. The value of ith entry in line number line is C(line, i). The value can be calculated using following formula.
C(line, i) = line! / ( (line-i)! * i! )
A simple method is to run two loops and calculate the value of Binomial Coefficient in inner loop.
C++
// C++ code for Pascal's Triangle #include <stdio.h> // for details of this function int binomialCoeff(int n, int k); // Function to print first // n lines of Pascal's // Triangle void printPascal(int n) { // Iterate through every line and // print entries in it for (int line = 0; line < n; line++) { // Every line has number of // integers equal to line // number for (int i = 0; i <= line; i++) printf("%d ", binomialCoeff(line, i)); printf("
"); } } // for details of this function int binomialCoeff(int n, int k) { int res = 1; if (k > n - k) k = n - k; for (int i = 0; i < k; ++i) { res *= (n - i); res /= (i + 1); } return res; } // Driver program int main() { int n = 7; printPascal(n); return 0; } |
Java
// Java code for Pascal's Triangle import java.io.*; class GFG { // Function to print first // n lines of Pascal's Triangle static void printPascal(int n) { // Iterate through every line // and print entries in it for (int line = 0; line < n; line++) { // Every line has number of // integers equal to line number for (int i = 0; i <= line; i++) System.out.print(binomialCoeff (line, i)+" "); System.out.println(); } } // Link for details of this function static int binomialCoeff(int n, int k) { int res = 1; if (k > n - k) k = n - k; for (int i = 0; i < k; ++i) { res *= (n - i); res /= (i + 1); } return res; } // Driver code public static void main(String args[]) { int n = 7; printPascal(n); } } /*This code is contributed by Nikita Tiwari.*/ |
Python3
# Python 3 code for Pascal's Triangle # A simple O(n^3) # program for # Pascal's Triangle # Function to print # first n lines of # Pascal's Triangle def printPascal(n) : # Iterate through every line # and print entries in it for line in range(0, n) : # Every line has number of # integers equal to line # number for i in range(0, line + 1) : print(binomialCoeff(line, i), " ", end = "") print() # for details of this function def binomialCoeff(n, k) : res = 1 if (k > n - k) : k = n - k for i in range(0 , k) : res = res * (n - i) res = res // (i + 1) return res # Driver program n = 7printPascal(n) # This code is contributed by Nikita Tiwari. |
C#
// C# code for Pascal's Triangle using System; class GFG { // Function to print first // n lines of Pascal's Triangle static void printPascal(int n) { // Iterate through every line // and print entries in it for (int line = 0; line < n; line++) { // Every line has number of // integers equal to line number for (int i = 0; i <= line; i++) Console.Write(binomialCoeff (line, i)+" "); Console.WriteLine(); } } // Link for details of this function static int binomialCoeff(int n, int k) { int res = 1; if (k > n - k) k = n - k; for (int i = 0; i < k; ++i) { res *= (n - i); res /= (i + 1); } return res; } // Driver code public static void Main() { int n = 7; printPascal(n); } } /*This code is contributed by vt_m.*/ |
PHP
<?php // PHP implementation for // Pascal's Triangle // for details of this function function binomialCoeff($n, $k) { $res = 1; if ($k > $n - $k) $k = $n - $k; for ($i = 0; $i < $k; ++$i) { $res *= ($n - $i); $res /= ($i + 1); } return $res; } // Function to print first // n lines of Pascal's // Triangle function printPascal($n) { // Iterate through every line and // print entries in it for ($line = 0; $line < $n; $line++) { // Every line has number of // integers equal to line // number for ($i = 0; $i <= $line; $i++) echo "".binomialCoeff($line, $i)." "; echo "
"; } } // Driver Code $n=7; printPascal($n); // This code is contributed by Mithun Kumar ?> |
Output :
1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1 1 6 15 20 15 6 1
Time complexity of this method is O(n^3). Following are optimized methods.
Method 2( O(n^2) time and O(n^2) extra space )
If we take a closer at the triangle, we observe that every entry is sum of the two values above it. So we can create a 2D array that stores previously generated values. To generate a value in a line, we can use the previously stored values from array.
C++
// C++ program for Pascal’s Triangle // A O(n^2) time and O(n^2) extra space // method for Pascal's Triangle #include <bits/stdc++.h> using namespace std; void printPascal(int n) { // An auxiliary array to store // generated pscal triangle values int arr[n][n]; // Iterate through every line and // print integer(s) in it for (int line = 0; line < n; line++) { // Every line has number of integers // equal to line number for (int i = 0; i <= line; i++) { // First and last values in every row are 1 if (line == i || i == 0) arr[line][i] = 1; // Other values are sum of values just // above and left of above else arr[line][i] = arr[line - 1][i - 1] + arr[line - 1][i]; cout << arr[line][i] << " "; } cout << "
"; } } // Driver code int main() { int n = 5; printPascal(n); return 0; } // This code is Contributed by Code_Mech. |
C
// C program for Pascal’s Triangle // A O(n^2) time and O(n^2) extra space // method for Pascal's Triangle void printPascal(int n) { // An auxiliary array to store // generated pscal triangle values int arr[n][n]; // Iterate through every line and print integer(s) in it for (int line = 0; line < n; line++) { // Every line has number of integers // equal to line number for (int i = 0; i <= line; i++) { // First and last values in every row are 1 if (line == i || i == 0) arr[line][i] = 1; // Other values are sum of values just // above and left of above else arr[line][i] = arr[line-1][i-1] + arr[line-1][i]; printf("%d ", arr[line][i]); } printf("
"); } } // Driver code int main() { int n = 5; printPascal(n); return 0; } |
Java
// java program for Pascal's Triangle // A O(n^2) time and O(n^2) extra // space method for Pascal's Triangle import java.io.*; class GFG { public static void main (String[] args) { int n = 5; printPascal(n); } public static void printPascal(int n) { // An auxiliary array to store generated pascal triangle values int[][] arr = new int[n][n]; // Iterate through every line and print integer(s) in it for (int line = 0; line < n; line++) { // Every line has number of integers equal to line number for (int i = 0; i <= line; i++) { // First and last values in every row are 1 if (line == i || i == 0) arr[line][i] = 1; else // Other values are sum of values just above and left of above arr[line][i] = arr[line-1][i-1] + arr[line-1][i]; System.out.print(arr[line][i]); } System.out.println(""); } } } |
C#
// C# program for Pascal's Triangle // A O(n^2) time and O(n^2) extra // space method for Pascal's Triangle using System; class GFG { public static void printPascal(int n) { // An auxiliary array to store // generated pascal triangle values int[,] arr = new int[n, n]; // Iterate through every line // and print integer(s) in it for (int line = 0; line < n; line++) { // Every line has number of // integers equal to line number for (int i = 0; i <= line; i++) { // First and last values // in every row are 1 if (line == i || i == 0) arr[line, i] = 1; else // Other values are sum of values // just above and left of above arr[line, i] = arr[line - 1, i - 1] + arr[line - 1, i]; Console.Write(arr[line, i]); } Console.WriteLine(""); } } // Driver Code public static void Main () { int n = 5; printPascal(n); } } // This code is contributed // by Akanksha Rai(Abby_akku) |
PHP
<?php // PHP program for Pascal’s Triangle // A O(n^2) time and O(n^2) extra space // method for Pascal's Triangle function printPascal($n) { // An auxiliary array to store // generated pscal triangle values $arr = array(array()); // Iterate through every line and // print integer(s) in it for ($line = 0; $line < $n; $line++) { // Every line has number of integers // equal to line number for ($i = 0; $i <= $line; $i++) { // First and last values in every row are 1 if ($line == $i || $i == 0) $arr[$line][$i] = 1; // Other values are sum of values just // above and left of above else $arr[$line][$i] = $arr[$line - 1][$i - 1] + $arr[$line - 1][$i]; echo $arr[$line][$i] . " "; } echo "
"; } } // Driver code $n = 5; printPascal($n); // This code is contributed // by Akanksha Rai ?> |
Output:
1 1 1 1 2 1 1 3 3 1 1 4 6 4 1
This method can be optimized to use O(n) extra space as we need values only from previous row. So we can create an auxiliary array of size n and overwrite values. Following is another method uses only O(1) extra space.
Method 3 ( O(n^2) time and O(1) extra space )
This method is based on method 1. We know that ith 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). It can be calculated in O(1) time using the following.
C(line, i) = line! / ( (line-i)! * i! ) C(line, i-1) = line! / ( (line - i + 1)! * (i-1)! ) We can derive following expression from above two expressions. C(line, i) = C(line, i-1) * (line - i + 1) / i So C(line, i) can be calculated from C(line, i-1) in O(1) time
C++
// C++ program for Pascal’s Triangle // A O(n^2) time and O(1) extra space // function for Pascal's Triangle #include <bits/stdc++.h> using namespace std; void printPascal(int n) { for (int line = 1; line <= n; line++) { int C = 1; // used to represent C(line, i) for (int i = 1; i <= line; i++) { // The first value in a line is always 1 cout<< C<<" "; C = C * (line - i) / i; } cout<<"
"; } } // Driver code int main() { int n = 5; printPascal(n); return 0; } // This code is contributed by Code_Mech |
C
// C program for Pascal’s Triangle // A O(n^2) time and O(1) extra space // function for Pascal's Triangle void printPascal(int n) { for (int line = 1; line <= n; line++) { int C = 1; // used to represent C(line, i) for (int i = 1; i <= line; i++) { printf("%d ", C); // The first value in a line is always 1 C = C * (line - i) / i; } printf("
"); } } // Driver code int main() { int n = 5; printPascal(n); return 0; } |
Java
// Java program for Pascal's Triangle // A O(n^2) time and O(1) extra // space method for Pascal's Triangle import java.io.*; class GFG { //Pascal function public static void printPascal(int n) { for(int line = 1; line <= n; line++) { int C=1;// used to represent C(line, i) 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(); } } //Diver code public static void main (String[] args) { int n = 5; printPascal(n); } } // This code is contributed // by Archit Puri |
Python3
# Python3 program for Pascal’s Triangle
# A O(n^2) time and O(1) extra
# space method for Pascal’s Triangle
# Pascal function
def printPascal(n):
for line in range(1, n + 1):
C = 1; # used to represent C(line, i)
for i in range(1, line + 1):
# The first value in a
# line is always 1
print(C, end = ” “);
C = int(C * (line – i) / i);
print(“”);
# Driver code
n = 5;
printPascal(n);
# This code is contributed by mits
C#
// C# program for Pascal's Triangle // A O(n^2) time and O(1) extra // space method for Pascal's Triangle using System; class GFG { // Pascal function public static void printPascal(int n) { for(int line = 1; line <= n; line++) { int C = 1;// used to represent C(line, i) for(int i = 1; i <= line; i++) { // The first value in a // line is always 1 Console.Write(C + " "); C = C * (line - i) / i; } Console.Write("
") ; } } // Driver code public static void Main () { int n = 5; printPascal(n); } } // This code is contributed // by ChitraNayal |
PHP
<?php // PHP program for Pascal's Triangle // A O(n^2) time and O(1) extra // space method for Pascal's Triangle // Pascal function function printPascal($n) { for($line = 1; $line <= $n; $line++) { $C = 1;// used to represent C(line, i) for($i = 1; $i <= $line; $i++) { // The first value in a // line is always 1 print($C . " "); $C = $C * ($line - $i) / $i; } print("
"); } } // Driver code $n = 5; printPascal($n); // This code is contributed by mits ?> |
Output:
1 1 1 1 2 1 1 3 3 1 1 4 6 4 1
So method 3 is the best method among all, but it may cause integer overflow for large values of n as it multiplies two integers to obtain values.
This article is compiled by Rahul and reviewed by GeeksforGeeks team. Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.
leave a comment
0 Comments