Pascal Triangle Program in C

What is a Pascal Triangle?

Pascal Triangle is a triangular arrangement (array) of numbers that shows the coefficients if a binomial expression is expanded. The numbers inside Pascal's triangle pattern are designed in such a way that each number will be the sum of the nearest two numbers in the above row of the triangle and the numbers at the extremes of each row of the triangle will be 1.

It is a triangular array of binomial coefficients which are widely used in the problems of algebra, probability theory, and Combinatorics. The Pascal triangle is a special triangle named after the french mathematician Blaise Pascal. Generally, the Pascal triangle is used to find the outcome of a coin, coefficients of binomial expansion in probability, etc.

Now let's learn more about the pattern of pascal's triangle with the help of an example.

Example of Pascal Triangle

Above is a representation of pascal's triangle in which the numbers are arranged in such a manner that we have 1's on both the extremes or sides of the triangle till the end. The numbers in the middle of the triangle are the sum of the two numbers in the above row. The topmost row in pascal's triangle is considered the 0th row of the triangle. Followed by the next row which is called the 1st and then the 2nd and so on. The element at the extreme left of a row is considered the 0th element in that row. With this convention, the number of elements inside the nth row is equal to (n+1) elements in that particular row.

Pascal's triangle is designed by having 1's as the first and last element of a row and by easily adding pair of successive numbers in the preceding row and then writing them in the new line.

How to Write Pascal Triangle Programs in C?

As we have discussed in previous sections Pascal's triangle is a special triangle having an arrangement of binomial coefficients. The numbers in the pascal triangle are arranged in such a way that each row of the triangle starts with 1 and the middle elements are the sum of the nearest two elements of the above row.

Now, let's understand how we can implement or write the Pascal triangle program in C language:

We will write a function to construct a pascal triangle in C which takes n as the input and prints the first n rows of Pascal's triangle.

We can implement the Pascal triangle in C in three different ways which are as follows:-

1. Brute Force approach
2. Optimized Time Complexity approach
3. Optimized Space Complexity approach

Now Let's understand every approach with its implementation.

Method 1: Brute Force

Introduction

In this approach, we will use a simple approach to print Pascal's triangle using the binomial theorem. Here we have used factorial and combination formulas to implement the Pascal Triangle program in C.

Now, let's see the code of the program to understand the approach more clearly.

Syntax

Output

Examples

The above Pascal triangle program in C is achieved using the formula of combination inside the program through the function combination(int n, int r). According to the above program, we have used the rows variable which is of int type and it denotes the number of rows of pascal's triangle to be printed.

Then inside main() method, we will call the function combination(). Inside the combination function, we are using the formula of combination i.e, (factorial(n) / ( factorial(n-r) * factorial(r)), where n is a number and we have to choose r numbers from n numbers. Now, this formula is applied to calculate the numbers to be inserted in pascal's triangle.

Complexity

• Since we are using three nested loops so the Time complexity of the above approach comes out to be $O(n^3)$.
• We are not using any extra space for printing Pascal's Triangle, so the Space Complexity of the above approach comes out to be O(1).

Method 2: Time Optimized $(O(n^2)$ Time and $O(n^2)$ Extra Space

Introduction

Unlike the above approach, here we will optimize our code and use a different approach to print Pascal's Triangle up to the required number of rows. As we know that every element in the middle of pascal's triangle is the sum of the above two elements. Therefore, in this approach, we will use a 2-Dimensional array that will store the values of previous rows so that we can utilize those values to generate values in the new row.

Now, let's take a look at the code to understand the optimized approach to implementing the pascal triangle program in C:

Syntax

Output

Examples

The above pascal triangle program in C is achieved using a 2-Dimensional array. Inside the 2-D array, we will store the values of the previous row and those values can be used to calculate the values in the next row. Then we used for loops to iterate through every row of the triangle and then we inserted 1 as the first and last value of every row. Now, we calculate the value of the middle elements by performing the sum of two elements of the above row in pascal's triangle. Then we print the required triangle up to a specified number of rows (rows) as seen in the output.

Complexity

• Since we are using two nested loops so the Time Complexity of the above approach comes out to be $O(n^2)$.
• Since we are using 2-Dimensional array so the Space complexity of the above approach comes out to be $O(n^2)$.

Method 3: Space Optimized

Introduction

Unlike the above approach, here we will use a more optimized approach to construct a pascal triangle program in C. As the first and last element of a row contains 1, we can calculate the remaining values of a row without using extra space.

Now, let's take a look at the code to understand a more optimized implementation of the pascal triangle program in C:

Syntax

Output

Examples

The above pascal triangle program in C can be achieved without using extra space. Here, we have used initialized the first and last values of every row as 1.

We have calculated the middle value using the first and last values. The formula that we have used is: B = B * (j - i) / i. After that, we printed the required triangle up to the specified number of rows (nRows provided in the input) in the output.

Complexity

• Since we are using two nested loops so the Time Complexity of the above approach comes out to be $O(n^2)$.
• We are not using any extra space for printing Pascal's Triangle, so the Space Complexity of the above approach comes out to be O(1).