Write a C program that take input from the user and displays pascal triangle.

The **Pascal Triangle** in C is a triangular pattern where the topmost element is 1, and subsequent numbers are generated by adding the two numbers above to form a new number in each row of the triangle.

**Example:**

Row no. 1. 1 -------------> Top of the triangle 2. 1 1 \+/ 3. 1 2 1 \+/ \+/ 4. 1 3 3 1 \+/ \+/ \+/ 5. 1 4 6 4 1 \+/ \+/ \+/ \+/ 6. 1 5 10 10 5 1

Pascal Triangle in C can be generated using various approaches, including the following techniques:

- Pascal Triangle in C using Naive Approach
- Pascal Triangle in C using Optimized Approach
- Pascal Triangle in C using Memorization
- Pascal Triangle in C using a 1 D Array

The idea behind this naive solution is to find the value of each array element that is equal to binomial coefficients.

**C(i , j) = [i! / (j!) * (i – j!)] ** (!=factorial sign, i=row number, j=column number)

**Example:**

1. Assume that, given **N=7**, the Outer loop **i** will run from 0 to N-1 =0,1,2,3,4,5,6. The inner loop **j** will run from 0 to i times.

2. The values will then be calculated using the formula below.

**C(i , j) = [i! / (j!) * (i – j!)] ** (!=factorial sign, i=row number, j=column number)

3. Put the result in the arr [i][j].

Row no. 0. 1 1. 1 1 2. 1 2 1 3. 1 3 3 1 4. 1 4 6 4 1 5. 1 5 10 10 5 1 6. 1 6 15 20 15 6 1

Here is the source code of the C program to print the pascals triangle using a naive approach. The C program is successfully compiled and run on a Linux system. The program output is also shown below.

/* Naive approach to Print Pascals Triangle. */ #include <stdio.h> long long int factorial(int); void main() { int rows; printf("Enter the Number of Rows in the Pascal Triangle::\t"); scanf("%d",&rows); int arr[rows][rows]; //initializing the array that will form base of the pascal triangle. for(int i=0;i<rows;i++) { for(int j=0;j<=i;j++) { arr[i][j]=(factorial(i)/(factorial(i-j)*factorial(j))); //Finding the value of iCj=[i!/(i-j!)*(j!)] for each place. } } for (int i = 0; i < rows; i++) { for (int k = rows - i-1 ; k > 0; k--) { //Prints spaces as many as number of rows in the triangle-current number of row printf(" "); } for (int j = 0; j <= i; j++) { printf("%-5d", arr[i][j]); // %-5d means length specifier. //it means 5 spaces are provided for number it fills spaces from left to right. } printf("\n"); } return ; } long long int factorial(int num) { long long int j=1; while(num>0) { j=j*num; num--; } return j; }

1. Take a number as input and store it in the variable row.

For example, Enter the Number of Rows in the Pascal Triangle:: 4

2. Initialize the array that will form the base of the Pascal triangle with row = row and column = row. It will be a square Matrix.

**arr [row][row] **

compiler makes **arr[4][4]**, array with 4 rows and 4 columns.

3. We ran an outer loop with counter variable **i** from **0** to row.

4. We ran an inner loop from **0** to **i** as the number of elements in a **row == i**.

5. The value of **arr[i][j] = factorial(i) / factorial(i-j) * factorial(j)**.

6. Factorial of a number => number*number-1*number-2*number*3*….*1.

7. The triangle contains some spaces that gradually decrease as we move down the pattern; the last row has 0 spaces, the second last has 1 space, and the third last has 2 spaces, so we can conclude that the number of spaces in the pattern’s row will be equal to (number of total rows – current row).

**Time Complexity: O(row ^{2}*N)**

The time complexity of the above program (Pascal Triangle) is O(row

^{2}*N) because the outer loop runs from 0 to rows and the inner loop runs close to row times on each iteration, and there is a factorial function that takes O(N) times where N = the number of digits in a number. Thus, we can conclude that the program is of cubic complexity.

**Space Complexity: O(row ^{2}+K)**

In this program, we are initializing a 2-d array that takes lot of storage. Therefore, our space complexity is quadratic function of number of rows, i.e.,

**O(row**, where K = Constant for auxiliary variables.

^{2}+k)**Testcase 1:** In this case, the entered value is “6” to print the pascal triangle.

Enter the Number of Rows in the Pascal Triangle:: 6 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1

**Testcase 2:** In this case, the entered value is “13” to print the pascal triangle.

Enter the Number of Rows in the Pascal Triangle:: 13 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 1 7 21 35 35 21 7 1 1 8 28 56 70 56 28 8 1 1 9 36 84 126 126 84 36 9 1 1 10 45 120 210 252 210 120 45 10 1 1 11 55 165 330 462 462 330 165 55 11 1 1 12 66 220 495 792 924 792 495 220 66 12 1

In this approach, we find the binomial coefficients and their addition is printed as Pascal’s triangle.

**Example:**

Given N=5

Then pascal triangle can be viewed as

Enter the number of rows: 5^{0}C_{0}= 1^{1}C_{0}= 1^{1}C_{1}= 1^{2}C_{0}= 1^{2}C_{1}= 2^{2}C_{2}= 1^{3}C_{0}= 1^{3}C_{1}= 3^{3}C_{2}= 3^{3}C_{3}= 1^{4}C_{0}= 1^{4}C_{1}= 4^{4}C_{2}= 6^{4}C_{3}= 4^{4}C_{4}= 1

As we can see in each rows, we expand the binomial theorem and find out the coefficient and print it out.

Here is source code of the C Program to display Pascal triangle using an optimized approach. The C Program is successfully compiled and run on a Linux system. The program output is also shown below.

#include<stdio.h> void Print_BinCoeff(int); //function to print the pattern line by line. int main() { int rows; printf("Enter the Number of Rows in the Pascal Triangle::\t"); scanf("%d",&rows); for(int i=0;i<rows;i++)//loop to iterate rows from 1 to rows { for (int k = rows - i-1 ; k > 0; k--) { //Prints spaces as many as number of rows in the triangle-current number of row printf(" "); } Print_BinCoeff(i);//function to print the binomial coefficients. } return 0; } void Print_BinCoeff(int x) { int temp=x; int answer=x; int c=2; for(int i=0;i<=x;i++) { if(i==0 || i==x) { printf("%-5d",1); } else { printf("%-5d",answer); //It's a length specifier, so it specifies the slot in which the number can be adjusted. answer=answer*(temp-1); answer=answer/c; temp--; c++; } } printf("\n"); }

In this approach, we find the binomial coefficients.

^{n}C_{r} = n!/((n-r)!*r!)

if r=0, ^{n}C_{r} = \(\frac{n!}{n-0! * 0!} = \frac{n!}{n! {0! = 1}}\)

hence ^{n}C_{0} = 1

if r==n, ^{n}C_{r} = \(\frac{n!}{(n-n!) n!} = \frac{n!}{0!*n!} = \frac{n!}{n!} = 1\)

hence ^{n}C_{n} = 1

thus, if r==0 or r==n then we can assume that ^{n}C_{r} = 1

to find the value of n!, the time complexity comes out to be O(n), but if we reduce the expression ^{n}C_{r} to a simpler quantity. Let’s look into it.

So, we see the row 4 => ^{4}C_{0} = 1; ^{4}C_{1} = 4; ^{4}C_{2} = 6; ^{4}C_{3} = 4; ^{4}C_{4} = 1

^{4}C_{0} = 1 {r==0};

^{4}C_{1} = \(\frac{4!}{1!} * 3! => \frac{4 * 3!}{3! * 1!} => \frac{4* 1}{1} => 4\)

^{4}C_{2} = \(\frac{4!}{2!} * 2! => \frac{4*3*2!}{2* 1 * 2!} => \frac{4* 3}{2 * 1} => 6\)

^{4}C_{3} = \(\frac{4!}{3!} * 1! => \frac{4*3*2 * 1!}{3* 2* 1 * 1!} => \frac{4* 3*2}{3* 2 * 1} => 4\)

^{4}C_{4} = 1 {r==n}

We can see a pattern being followed here:

^{4}C_{1} = \(\frac{4*1}{1}\); ^{4}C_{2} = \(\frac{4*3}{2}\); ^{4}C_{3} = \(\frac{4*3*2}{2*3}\)

Using this method, we can store intermediate results in auxiliary variables and reduce the complexity of determining the value of next terms.

**Time Complexity: O(rows ^{2})**

The above program for printing the pascal triangle pattern will take a O(n

^{2}) time as outer loop i runs from 0 to rows, and inner loop 1, runs from 0 to rows-i times and inner loop 2*j iterates from 0 to i. So, at the algorithm runs for rows

^{2}times (approx.).

**Space Complexity: O(1)**

In this program we are not initializing any array or other data types that takes lot of storage. We are just initializing the variable. Therefore, our space complexity is constant, i.e. O(1).

Enter the Number of Rows in the Pascal Triangle:: 12 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 1 7 21 35 35 21 7 1 1 8 28 56 70 56 28 8 1 1 9 36 84 126 126 84 36 9 1 1 10 45 120 210 252 210 120 45 10 1 1 11 55 165 330 462 462 330 165 55 11 1

This is an optimized approach to print Pascal triangle through Memorization.

Here is source code of the C Program to display Pascal triangle through Memorization. The C program is successfully compiled and run on a Linux system. The program output is also shown below.

/* * C Program to Display Pascal triangle */ #include <stdio.h> void main() { int array[15][15], i, j, rows, num = 25, k; printf("\n Enter the number of rows:"); scanf("%d", &rows); for (i = 0; i < rows; i++) { for (k = num - 2 * i; k >= 0; k--) printf(" "); for (j = 0; j <= i; j++) { if (j == 0 || i == j) { array[i][j] = 1; } else { array[i][j] = array[i - 1][j - 1] + array[i - 1][j]; } printf("%4d", array[i][j]); } printf("\n"); } }

This C program is used to print the Pascal triangle. Pascal’s triangle is a triangular array of the binomial coefficients. The program consists of six integer type of variable, named **i, j, rows, array[][], k and num**.

Out of these variable **i, j and k** have been defined to control the **for()** loop, the integer ‘**rows**’ stores the limit of Pascal’s triangle entered by the user. As the program for Pascal’s triangle is executed, it first asks for the value of limit of the triangle.

The program assigns ‘**rows**’ variable value with ‘**i**’ variable value, i.e., number of space with the limit of Pascal’s triangle, for loop in which ‘**i**’ is the loop control variable. Again, in order to control the space, a nested for loop with ‘**k**’ as a control variable is used.

Finally, for printing the elements in this program for Pascal’s triangle in C, another nested **for()** loop of control variable ‘**j**’ has been used. The formula used to generate the numbers of

Pascal’s triangle is: **array[i][j] = array[i – 1][j – 1] + array[i – 1][j]**

After printing one complete row of numbers of Pascal’s triangle, the control comes out of the nested loops and goes to next line as commanded by ‘\n’ code. The process repeats till the control number specified is reached.

**Time Complexity: O(rows ^{2})**

The above program for printing the pascal triangle pattern will take a O(n

^{2}) time as outer loop i runs from 0 to rows, and inner loop 1, runs from 0 to rows-i times and inner loop 2*j iterates from 0 to i. As a result, the algorithm runs for rows

^{2}times (approx.).

**Space Complexity: O(n ^{2})**

In this program, we are initialising a 2-d array in memory. As a result, our space complexity is quadratic, i.e., O(n

^{2}), where N=number of rows in the matrix.

Output: Enter the number of rows: 3 1 1 1 1 2 1

In this approach, we print pascal triangle using 1 D Array.

Here is source code of the C Program to display Pascal triangle using 1 D Array. The C program is successfully compiled and run on a Linux system. The program output is also shown below.

`/*`

`* C Program to Generate Pascal Triangle 1 D Array`

`*/`

`#include <stdio.h>`

void main()

`{`

int array[30], temp[30], i, j, k, l, num; //using 2 arrays

printf("Enter the number of lines to be printed: ");

scanf("%d", &num);

temp[0] = 1;

array[0] = 1;

for (j = 0; j < num; j++)

printf(" ");

printf(" 1\n");

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

`{`

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

printf(" ");

for (k = 1; k < num; k++)

`{`

array[k] = temp[k - 1] + temp[k];

`}`

array[i] = 1;

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

`{`

printf("%3d", array[l]);

temp[l] = array[l];

`}`

printf("\n");

`}`

`}`

Enter the number of lines to be printed: 4 1 1 1 1 2 1 1 3 3 1

To practice programs on every topic in C, please visit “Programming Examples in C”, “Data Structures in C” and “Algorithms in C”.

**Related Posts:**

- Apply for C Internship
- Practice Computer Science MCQs
- Apply for Computer Science Internship
- Check Computer Science Books
- Check C Books