Pascal's Triangle Little Mathematics Library Pdf

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

Become a success story instead of just reading about them. Prepare for coding interviews at Amazon and other top product-based companies with our Amazon Test Series. Includes topic-wise practice questions on all important DSA topics along with 10 practice contests of 2 hours each. Designed by industry experts that will surely help you practice and sharpen your programming skills. Wait no more, start your preparation today!

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 i th 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++

#include <iostream>

using namespace std;

int binomialCoeff( int n, int k);

void printPascal( int n)

{

for ( int line = 0; line < n; line++)

{

for ( int i = 0; i <= line; i++)

cout << " " << binomialCoeff(line, i);

cout << "\n" ;

}

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;

}

int main()

{

int n = 7;

printPascal(n);

return 0;

}

C

#include <stdio.h>

int binomialCoeff( int n, int k);

void printPascal( int n)

{

for ( int line = 0; line < n; line++)

{

for ( int i = 0; i <= line; i++)

printf ( "%d " ,

binomialCoeff(line, i));

printf ( "\n" );

}

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;

}

int main()

{

int n = 7;

printPascal(n);

return 0;

}

Java

import java.io.*;

class GFG {

static void printPascal( int n)

{

for ( int line = 0 ; line < n; line++)

{

for ( int i = 0 ; i <= line; i++)

System.out.print(binomialCoeff

(line, i)+ " " );

System.out.println();

}

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;

}

public static void main(String args[])

{

int n = 7 ;

printPascal(n);

}

Python3

def printPascal(n) :

for line in range ( 0 , n) :

for i in range ( 0 , line + 1 ) :

print (binomialCoeff(line, i),

" " , end = "")

print ()

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

n = 7

printPascal(n)

C#

using System;

class GFG {

static void printPascal( int n)

{

for ( int line = 0; line < n; line++)

{

for ( int i = 0; i <= line; i++)

Console.Write(binomialCoeff

(line, i)+ " " );

Console.WriteLine();

}

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;

}

public static void Main()

{

int n = 7;

printPascal(n);

}

PHP

<?php

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 printPascal( $n )

{

for ( $line = 0; $line < $n ; $line ++)

{

for ( $i = 0; $i <= $line ; $i ++)

echo "" .binomialCoeff( $line , $i ). " " ;

echo "\n" ;

}

$n =7;

printPascal( $n );

?>

Javascript

<script>

function printPascal(n)

{

for (let line = 0; line < n; line++)

{

for (let i = 0; i <= line; i++)

document.write(binomialCoeff

(line, i)+ " " );

document.write( "<br />" );

}

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;

}

let n = 7;

printPascal(n);

</script>

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

Auxiliary Space: O(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++

#include <bits/stdc++.h>

using namespace std;

void printPascal( int n)

{

int arr[n][n];

for ( int line = 0; line < n; line++)

{

for ( int i = 0; i <= line; i++)

{

if (line == i || i == 0)

arr[line][i] = 1;

else

arr[line][i] = arr[line - 1][i - 1] +

arr[line - 1][i];

cout << arr[line][i] << " " ;

}

cout << "\n" ;

}

int main()

{

int n = 5;

printPascal(n);

return 0;

}

C

void printPascal( int n)

{

int arr[n][n];

for ( int line = 0; line < n; line++)

{

for ( int i = 0; i <= line; i++)

{

if (line == i || i == 0)

arr[line][i] = 1;

else

arr[line][i] = arr[line-1][i-1] + arr[line-1][i];

printf ( "%d " , arr[line][i]);

}

printf ( "\n" );

}

int main()

{

int n = 5;

printPascal(n);

return 0;

}

Java

import java.io.*;

class GFG {

public static void main (String[] args) {

int n = 5 ;

printPascal(n);

}

public static void printPascal( int n)

{

int [][] arr = new int [n][n];

for ( int line = 0 ; line < n; line++)

{

for ( int i = 0 ; i <= line; i++)

{

if (line == i || i == 0 )

arr[line][i] = 1 ;

else

arr[line][i] = arr[line- 1 ][i- 1 ] + arr[line- 1 ][i];

System.out.print(arr[line][i]);

}

System.out.println( "" );

}

Python3

def printPascal(n: int ):

arr = [[ 0 for x in range (n)]

for y in range (n)]

for line in range ( 0 , n):

for i in range ( 0 , line + 1 ):

if (i is 0 or i is line):

arr[line][i] = 1

print (arr[line][i], end = " " )

else :

arr[line][i] = (arr[line - 1 ][i - 1 ] +

arr[line - 1 ][i])

print (arr[line][i], end = " " )

print ( "\n" , end = "")

n = 5

printPascal(n)

C#

using System;

class GFG

{

public static void printPascal( int n)

{

int [,] arr = new int [n, n];

for ( int line = 0; line < n; line++)

{

for ( int i = 0; i <= line; i++)

{

if (line == i || i == 0)

arr[line, i] = 1;

else

arr[line, i] = arr[line - 1, i - 1] +

arr[line - 1, i];

Console.Write(arr[line, i]);

}

Console.WriteLine( "" );

}

public static void Main ()

{

int n = 5;

printPascal(n);

}

PHP

<?php

function printPascal( $n )

{

$arr = array ( array ());

for ( $line = 0; $line < $n ; $line ++)

{

for ( $i = 0; $i <= $line ; $i ++)

{

if ( $line == $i || $i == 0)

$arr [ $line ][ $i ] = 1;

else

$arr [ $line ][ $i ] = $arr [ $line - 1][ $i - 1] +

$arr [ $line - 1][ $i ];

echo $arr [ $line ][ $i ] . " " ;

}

echo "\n" ;

}

$n = 5;

printPascal( $n );

?>

Javascript

<script>

var n = 5;

printPascal(n);

function printPascal(n)

{

arr = a = Array(n).fill(0).map(x => Array(n).fill(0));

for (line = 0; line < n; line++)

{

for (i = 0; i <= line; i++)

{

if (line == i || i == 0)

arr[line][i] = 1;

else

arr[line][i] = arr[line-1][i-1] + arr[line-1][i];

document.write(arr[line][i]);

}

document.write( "<br>" );

}

</script>

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 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). 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++

#include <bits/stdc++.h>

using namespace std;

void printPascal( int n)

{

for ( int line = 1; line <= n; line++)

{

int C = 1;

for ( int i = 1; i <= line; i++)

{

cout<< C<< " " ;

C = C * (line - i) / i;

}

cout<< "\n" ;

}

int main()

{

int n = 5;

printPascal(n);

return 0;

}

C

void printPascal( int n)

{

for ( int line = 1; line <= n; line++)

{

int C = 1;

for ( int i = 1; i <= line; i++)

{

printf ( "%d " , C);

C = C * (line - i) / i;

}

printf ( "\n" );

}

int main()

{

int n = 5;

printPascal(n);

return 0;

}

Java

import java.io.*;

class GFG {

public static void printPascal( int n)

{

for ( int line = 1 ; line <= n; line++)

{

int C= 1 ;

for ( int i = 1 ; i <= line; i++)

{

System.out.print(C+ " " );

C = C * (line - i) / i;

}

System.out.println();

}

public static void main (String[] args) {

int n = 5 ;

printPascal(n);

}

Python3

def printPascal(n):

for line in range ( 1 , n + 1 ):

C = 1 ;

for i in range ( 1 , line + 1 ):

print (C, end = " " );

C = int (C * (line - i) / i);

print ("");

n = 5 ;

printPascal(n);

C#

using System;

class GFG

{

public static void printPascal( int n)

{

for ( int line = 1;

line <= n; line++)

{

int C = 1;

for ( int i = 1; i <= line; i++)

{

Console.Write(C + " " );

C = C * (line - i) / i;

}

Console.Write( "\n" ) ;

}

public static void Main ()

{

int n = 5;

printPascal(n);

}

PHP

<?php

function printPascal( $n )

{

for ( $line = 1; $line <= $n ; $line ++)

{

$C = 1;

for ( $i = 1; $i <= $line ; $i ++)

{

print ( $C . " " );

$C = $C * ( $line - $i ) / $i ;

}

print ( "\n" );

}

$n = 5;

printPascal( $n );

?>

Javascript

<script>

function printPascal(n)

{

for (line = 1; line <= n; line++)

{

var C=1;

for (i = 1; i <= line; i++)

{

document.write(C+ " " );

C = C * (line - i) / i;

}

document.write( "<br>" );

}

var n = 5;

printPascal(n);

</script>

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.