Pascal Triangle Program in C

Problem Description

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

What is 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
Problem Solution

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

Method 1: (Naive Approach)
advertisement
advertisement

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
Program/Source Code

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;
}
Program Explanation

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(row2*N)
The time complexity of the above program (Pascal Triangle) is O(row2*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(row2+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(row2+k), where K = Constant for auxiliary variables.

Runtime Test Cases
advertisement

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

Method 2: (Optimized Approach)
advertisement

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
                          0C0 =    1
                       1C0 =    1   1C1 = 1
                     2C0 =    1  2C1 =  2    2C2 = 1
                  3C0 = 1   3C1 =   3    3C2 = 3    3C3  = 1
              4C0 = 1  4C1 =  4    4C2 = 6   4C3 = 4  4C4  = 1

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

Program/Source Code

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");
}
Program Explanation

In this approach, we find the binomial coefficients.
nCr = n!/((n-r)!*r!)

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

hence nC0 = 1

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

hence nCn = 1

thus, if r==0 or r==n then we can assume that nCr = 1

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

So, we see the row 4 => 4C0 = 1; 4C1 = 4; 4C2 = 6; 4C3 = 4; 4C4 = 1

4C0 = 1 {r==0};

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

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

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

4C4 = 1 {r==n}

We can see a pattern being followed here:

4C1 = \(\frac{4*1}{1}\); 4C2 = \(\frac{4*3}{2}\); 4C3 = \(\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(rows2)
The above program for printing the pascal triangle pattern will take a O(n2) 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 rows2 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).

Runtime Test Cases
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

Method 3: (Optimized Approach through Memorization)

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

Program/Source Code

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");
    }
}
Program Explanation

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(rows2)
The above program for printing the pascal triangle pattern will take a O(n2) 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 rows2 times (approx.).

Space Complexity: O(n2)
In this program, we are initialising a 2-d array in memory. As a result, our space complexity is quadratic, i.e., O(n2), where N=number of rows in the matrix.

Runtime Test Cases
 
Output:
 
Enter the number of rows: 3
                             1
                           1   1
                        1    2    1

Method 4: (Pascal Triangle using 1 D Array)

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

Program/Source Code

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.

  1. /*
  2.  * C Program to Generate Pascal Triangle 1 D Array
  3.  */
  4. #include <stdio.h>
  5.  
  6. void main()
  7. {
  8.     int array[30], temp[30], i, j, k, l, num;  //using 2 arrays
  9.  
  10.     printf("Enter the number of lines to be printed: ");
  11.     scanf("%d", &num);
  12.     temp[0] = 1;
  13.     array[0] = 1;
  14.     for (j = 0; j < num; j++)
  15.         printf(" ");
  16.     printf(" 1\n");
  17.     for (i = 1; i < num; i++)
  18.     {
  19.         for (j = 0; j < i; j++)
  20.             printf(" ");
  21.         for (k = 1; k < num; k++)
  22.         {
  23.             array[k] = temp[k - 1] + temp[k];      
  24.         }
  25.         array[i] = 1;
  26.         for (l = 0; l <= i; l++)
  27.         {
  28.             printf("%3d", array[l]);
  29.             temp[l] = array[l];
  30.         }
  31.         printf("\n");
  32.     }
  33. }
Program Output
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”.

If you find any mistake above, kindly email to [email protected]

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.