Pascal’s triangle is a triangular array of binomial coefficients. Write a function that takes an integer value N as input and prints the first N lines of Pascal’s triangle.
Example:
The below image shows the Pascal’s Triangle for N=6
Pascal’s Triangle using Binomial Coefficient:
The 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! )
Algorithm:
- Run a loop for each row of pascal’s triangle i.e. 1 to N.
- For each row, run an internal loop for each element of that row.
- Calculate the binomial coefficient for the element using the formula mentioned in the approach.
- For each row, run an internal loop for each element of that row.
Below is the implementation of the above approach:
C++
// C++ code for Pascal's Triangle#include <iostream>using namespace std;int binomialCoeff(int n, int k);// Function to print first// n lines of Pascal's// Trianglevoid 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++) cout << " " << binomialCoeff(line, i); cout << "\n"; }}// See// for details of this functionint 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 programint main(){ int n = 7; printPascal(n); return 0;}// This code is contributed by shivanisinghss2110 |
C
// C++ code for Pascal's Triangle#include <stdio.h>// for details of this functionint binomialCoeff(int n, int k);// Function to print first// n lines of Pascal's // Trianglevoid 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("\n"); }}// for details of this functionint 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 Triangleimport 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 Triangledef 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 functiondef 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 programn = 7printPascal(n)# This code is contributed by Nikita Tiwari. |
C#
// C# code for Pascal's Triangleusing 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.*/ |
Javascript
<script>// Javascript code for Pascal's Triangle // Function to print first // n lines of Pascal's Triangle function printPascal(n) { // Iterate through every line // and print entries in it for (let line = 0; line < n; line++) { // Every line has number of // integers equal to line number for (let i = 0; i <= line; i++) document.write(binomialCoeff (line, i)+" "); document.write("<br />"); } } // Link for details of this function function binomialCoeff(n, k) { let res = 1; if (k > n - k) k = n - k; for (let i = 0; i < k; ++i) { res *= (n - i); res /= (i + 1); } return res; }// Driver Code let n = 7; printPascal(n);</script> |
PHP
<?php// PHP implementation for// Pascal's Triangle// for details of this functionfunction 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 // Trianglefunction 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 "\n"; }}// 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: O(N^3), where N is the number of rows you want to print
Auxiliary Space: O(1)
Pascal’s Triangle using Dynamic Programming:
If we take a closer at the triangle, we observe that every entry is sum of the two values above it. So using dynamic programming we can create a 2D array that stores previously generated values. In order to generate a value in a line, we can use the previously stored values from array.
Cases:
- If line == 0 or line == i
- arr[line][i] =1
- Else:
- arr[line][i] = arr[line-1][i-1] + arr[line-1][i]
Below is the implementation of the above approach:
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 pascal 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 << "\n"; }}// Driver codeint 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 Trianglevoid printPascal(int n){// An auxiliary array to store // generated pascal triangle valuesint arr[n][n]; // Iterate through every line and print integer(s) in itfor (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("\n");}}// Driver codeint 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 Triangleimport 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 valuesint[][] arr = new int[n][n]; // Iterate through every line and print integer(s) in itfor (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("");}}} |
Python3
# Python3 program for Pascal's Triangle# A O(n^2) time and O(n^2) extra # space method for Pascal's Triangledef printPascal(n:int): # An auxiliary array to store # generated pascal triangle values arr = [[0 for x in range(n)] for y in range(n)] # Iterate through every line # and print integer(s) 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): # First and last values # in every row are 1 if(i is 0 or i is line): arr[line][i] = 1 print(arr[line][i], end = " ") # 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]) print(arr[line][i], end = " ") print("\n", end = "")# Driver Coden = 5printPascal(n)# This code is contributed # by Sanju Maderna |
C#
// C# program for Pascal's Triangle// A O(n^2) time and O(n^2) extra // space method for Pascal's Triangleusing System;class GFG {public static void printPascal(int n){ // An auxiliary array to store // generated pascal triangle valuesint[,] arr = new int[n, n]; // Iterate through every line// and print integer(s) in itfor (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 Codepublic static void Main () { int n = 5; printPascal(n);}}// This code is contributed // by Akanksha Rai(Abby_akku) |
Javascript
<script>// javascript program for Pascal's Triangle// A O(n^2) time and O(n^2) extra // space method for Pascal's Trianglevar n = 5;printPascal(n);function printPascal(n){// An auxiliary array to store generated pascal triangle valuesarr = a = Array(n).fill(0).map(x => Array(n).fill(0));// Iterate through every line and print integer(s) in itfor (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; 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]; document.write(arr[line][i]); } document.write("<br>");}}// This code is contributed by 29AjayKumar </script> |
PHP
<?php// PHP program for Pascal’s Triangle// A O(n^2) time and O(n^2) extra space // method for Pascal's Trianglefunction printPascal($n){ // An auxiliary array to store // generated pascal 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 "\n"; }}// 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
Time Complexity: O(N^2)
Auxiliary Space: O(N^2)
Note: 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.
Pascal’s Triangle using Binomial Coefficient (Space Optimised):
This method is based on approach using Binomial Coefficient. 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.
- 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
below is the implementation of the approach:
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 << "\n"; }}// Driver codeint 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 Trianglevoid 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("\n");}}// Driver codeint 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 Triangleimport 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(); }}// Driver codepublic 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("\n") ; } } // Driver code public static void Main (){ int n = 5; printPascal(n); } } // This code is contributed// by ChitraNayal |
Javascript
<script>// JavaScript 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++) { var C=1;// used to represent C(line, i) for(i = 1; i <= line; i++) { // The first value in a line is always 1 document.write(C+" "); C = C * (line - i) / i; } document.write("<br>"); }}// Driver codevar n = 5;printPascal(n);// This code is contributed by 29AjayKumar </script> |
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("\n"); } } // 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
Time Complexity: O(n2)
Auxiliary Space: O(1)
Variations of the problem that may be asked in interviews:
- Find the whole pascal triangle as shown above.
- Find just the one element of a pascal’s triangle given row number and column number in O(n) time.
- Find a particular row of pascal’s triangle given a row number in O(n) time.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
