Find pascal triangle upto nth depth in C++

Post Views: 537

Pascal’s triangle is a special arrangement of coefficients of the expansion of any binomial expression, such as (x+y)ⁿ . The binomial coefficients formed are written row-wise based on the values taken by n to form the triangular shape. The number of coefficients(or entries) in each line is one greater than the row number(same as the value of (n+1)). For example, the coefficients for row number 0 will be [1], row number 1 will be [1, 1 ], row number 2 will be [1,2,1], row number 3 will be [1,3,3,1], and so on.

Considering we start counting row number and position from 0(similar to the indexing of arrays in C++) for any entry, the formula for the coefficient in row number ‘r’ and position ‘p’ can be given by rCp = (r)!/((r-p)!*(p!)). For example, the entry at row number 3 and 2nd position is (3!/((3-2)!*(2!))=3.

Let us move towards our goal of creating such a Pascal triangle using C++.

Simpler Approach:

The most basic idea, we can think of for building this triangle is by going through each row and position and calculating the value of the binomial coefficient until we complete the required number of rows.

Step1: We will be running through all the rows from (0 to n-1) that can be achieved by a loop.

Step2: For each row, we will again run a loop for position value (0 to (row number-1)).

Step3: Calculate the binomial coefficient at the respective row and position.

Note: The value of the binomial coefficient at any row and position can be given by rCp = (r!)/((r-p)!*(p!)) = (r/1)*((r-1)/2)*....*((r-(p-1))/p)

C++ code for implementation of the above steps:

#include <bits/stdc++.h>
using namespace std;

int BinoCoeff(int r, int p){ 
    //The function for calculating binomial coefficient is declared.
    int ans = 1;
    
    //Using the concept 
    //rCp = (r)!/((r-p)!*(p!)) = (r/1)*((r-1)/2)*....*((r-(p-1))/p)
    for(int i=0; i<p; ++i){
        ans *= (r-i);          // Will take care of the numerator
        ans /= (i+1);         // Will take care of the denominator
    }
    
    
    return ans; // The value is returned
}


int main() {
    int n;
    cin>>n; //Taking input for number of rows to be printed
    
    for(int r=0; r<n; r++){
        cout << "row " << r <<"-> "; //Printing the row number
        for(int p=0; p<=r; p++){
            cout << BinoCoeff(r, p) <<" "; //Calling out the function for calculating
                                           //binomial coefficient at respective row and position.
        }
        cout<<endl;// To move to next row
    }
    return 0;
}

Input:

Output:

row 0-> 1 
row 1-> 1 1 
row 2-> 1 2 1 
row 3-> 1 3 3 1 
row 4-> 1 4 6 4 1 
row 5-> 1 5 10 10 5 1

Time Complexity: O(n^3) (As we are iterating over n rows, n positions for that particular row, and while calculating also we iterate through n values for p in BinoCoeff Function.)

Space Complexity : O(1)

Smarter Approach:

If we take a closer look at the expression BinoCoeff(r, p) = rCp = (r!)/((r-p)!*(p!)) = (r/1)*((r-1)/2)*....*((r-(p-1))/p), we do notice a relation between BinoCoeff(r, p) and BinoCoeff(r, (p-1)). Where BinoCoeff(r, p)=(r!)/((r-p)!*(p!)) and BinoCoeff(r, (p-1))=(r!)/((r-p+1)!*(p-1)!). Hence we can say, BinoCoeff(r, p) = BinoCoeff(r, p-1)*((r-p+1)/p). .....(@)

Note: We will be iterating row from 1 to n instead of 0 to (n-1) as in the formula above (@). So, the value of row = r+1 and therefore, BinoCoeff(row, pos) = BinoCoeff(row, pos-1)*((row-pos)/pos) will be used for coding.

C++ code: Find pascal triangle upto nth depth

#include <bits/stdc++.h>
using namespace std;

void printPT(int n){
   for(int row=1; row<=n; row++){
       cout << "row "<< row-1 << "-> "; // printing row number
       int Coeff = 1;         // First element of a row is always 1
       for(int pos=1; pos<=row; pos++){
           cout << Coeff<<" ";    //Print Coeff
           Coeff = Coeff*(row-pos)/pos; //Calculate next Coeff 
           //(We used (row-p) instead of (row-p+1), because our "row" here is different from row in formula.)
           // row in formula was iterating from 0 to n-1, here its from 1 to n
       }
       cout << endl; // To move to next line for new row
   } 
}



int main() {
    int n;
    cin>>n; //Taking input for number of rows to be printed
    printPT(n); //Function called for printing Pascal Triangle
    
    return 0;
}