Tutorialspoint.dev

Pascal’s Triangle

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>
  
// See https://tutorialspoint.dev/slugresolver/space-and-time-efficient-binomial-coefficient/ 
// 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(" ");
    }
}
  
// See https://tutorialspoint.dev/slugresolver/space-and-time-efficient-binomial-coefficient/
// 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
    // https://tutorialspoint.dev/slugresolver/space-and-time-efficient-binomial-coefficient/
    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.*/

/div>

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()
      
  
# See https://tutorialspoint.dev/slugresolver/space-and-time-efficient-binomial-coefficient/
# 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 = 7
printPascal(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
    // https://tutorialspoint.dev/slugresolver/space-and-time-efficient-binomial-coefficient/
    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.



This article is attributed to GeeksforGeeks.org

tags:

Arrays Mathematical Adobe binomial coefficient pattern-printing Adobe Arrays Mathematical pattern-printing
Prev Next
More topics on Mathematical Algorithms

You Might Also Like

leave a comment

code

0 Comments

load comments

Subscribe to Our Newsletter

Top Followed books

Mathematical Algor... Recursive program for prime nu...
Mathematical Algor... Sum of all proper divisors of ...
Mathematical Algor... Sum of Fibonacci Numbers
Mathematical Algor... Program for Fibonacci numbers
Mathematical Algor... Check if a number is a Krishna...
Mathematical Algor... Prime numbers and Fibonacci