Pascal Triangle in C

• The pascal triangle in c is an array of binomial coefficients in triangular form. Here the nth row contains the binomial coefficient of ncr.
• In a pascal triangle, every number is obtained by summing the two numbers above it.

Example:

• There are two different ways to obtain the pascal triangle in c, They are
• Using 2d array
• Using combination

Using 2d Arrays

• Here every number is the sum of the above two numbers, To store the values obtained, we create a 2d array.
• To obtain a value,we use stored values from the array.
• The time complexity for generating the pascal triangle is O(n2).
• The space complexity for generating the pascal triangle is O(1).

Program:

``````/ / program to print pascal triangle
/ / using 2d array method
#include <stdio.h>
/ / pascal function
Void pascal ( int n )
{
/ / defining a array to store
Int a [n] [n];
for ( inti = 0 ; i< n; i++)
{
for ( int j = 0;j <= i; j++)
{
If ( i == j | | j == 0)
a [i] [j] = 1;
else
a [i] [j] = ( a [i -1][j – 1] + a [i -1][j];
printf(“%d ” , a [i][j] );
}
Printf( “\n” );
} }
/ / main method
int main ( ) {
int n = 5;
pascal (n);
return 0;
}
``````

Output:

``````1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
``````

2. combination method:

• In this method, C(n,r) is used to represent the nth row of nth element in pascal triangle.
• The formula to calculate is :

C(n,r) = C(n, r - 1) * (n – r + 1 ) / r

Program:

``````#include <stdio.h>
Void pascal ( int n )
{
for ( inti = 1;i <= n;i++)
{
Int c = 1;
for ( int j = 1; j <= i; j++ )
{
Printf( “ %d ”, c);
c = c * (i – j) / j;
}
Printf(“ \n”);  }  }
/ /  main method
int main ( ) {
int n = 5;
pascal (n);
return 0;
}

``````

Output:

``````1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
``````
• Here the element in the pascal triangle is calculated in O(1) time using the above formula.
• The time complexity for generating the pascal triangle is O(n2).
• The space complexity for generating the pascal triangle is O(1).