Program to Print Pascal's Triangle in Pattern.

Pascal Triangle is basically a triangular array formed by Binomial Coefficients. Here in this post, we will learn how to print Pascal Triangle using C++ programming language. Before going to the code section let us first understand the formation of the pascal triangle with one example.

Example of Pascal Triangle

If you observe the above triangular pattern carefully then you will observe that there is a rule for creating this Pascal Triangle.

The rule for creating a Pascal Triangle is to start with the number 1 at level 0 and to get your next number for the following levels you need to add the two consecutive numbers that are present on the above left and above right side of it. (alert-success)
1 2
\ + /
3

Approach 1: Using O(n^2) extra space.

Here we are going to use one extra 2D array to store the previously generated values so we can use them to calculate binomial coefficient values for the next upcoming rows. Sum the two above two consecutive numbers to get the next number.

C++ Code for Printing Pascal Triangle:

//C++ Program to Print Pascal Triangle using O(n^2) extra space
#include<iostream>
using namespace std;

void pascalTriangle(int n){
    int arr[n][n];

    cout<<"Print Pascal Triangle: "<<endl;
    for(int i = 0; i < n; i++){
        for(int j = 1; j < (n - i); j++){
            cout<<" ";
        }
        for(int k = 0; k <= i; k++){
            if(i == k || k == 0){
                arr[i][k] = 1;
            }
            else{
                arr[i][k] = arr[i - 1][k - 1] + arr[i - 1][k];
            }
            cout<<" "<<arr[i][k];
        }
        cout<<"\n";
    }
}
int main(){
    int n = 5;
    pascalTriangle(n);
}

Output:

Print Pascal Triangle:  
                  1
 
               1      1
 
            1      2      1
 
         1      3      3      1
 
      1      4      6      4      1

Time Complexity: (n^2)
Space Complexity: (n^2)

Approach 2: Without using extra Space.

Here we are simply using going to run two nested loops and going to calculate the binomial coefficient using the below formula in the inner loop.

C++ Code for Printing Pascal Triangle:

//Print Pascal Triangle in without using extra space in C++
#include<iostream>
using namespace std;

void pascalTriangle(int n){
    int row = n;

    cout<<"Print Pascal Triangle: "<<endl;;
    for(int i = 0; i < row; i++){
        int value = 1;
        for(int j = 1; j < (row -i); j++){
            cout<<" ";
        }
        for(int k = 0; k <= i; k++){
            cout<<" "<<value;
            value = value * (i - k)/(k + 1);
        }
        cout<<endl<<endl;
    }
}

int main(){
    int n = 5;
    pascalTriangle(n);

    return 0;
}

Output:

Print Pascal Triangle:  
                  1
 
               1      1
 
            1      2      1
 
         1      3      3      1
 
      1      4      6      4      1

Time Complexity: (n^2)
Space Complexity: (1)

I hope you found this post useful, please do share your valuable feedback in the comment section below and help us improve our content for you.

Next:

(getButton) #text=(Program to Find Transpose of 2D Matrix) #icon=(link) #color=(#2339bd)

Program to Print Pascal's Triangle in Pattern.

Approach 1: Using O(n^2) extra space.

Approach 2: Without using extra Space.

No comments:

Post a Comment