Pascal's Triangle
Objective
Write a C++ program to print Pascal's Triangle using a factorial function.
Algorithm / Approach
- Create a
fact()function to calculate factorials. - In
main(), use nested loops to print spaces to center the triangle. - Use an inner loop
cto calculate and print the combination formula:fact(i) / (fact(c) * fact(i - c)).
main.cpp
#include<iostream>
using namespace std;
int fact(int x) {
int res = 1;
for(int i = 1; i< x; i++) {
res = res*i;
}
return res;
}
int main() {
int n;
cout<<"Enter the value for N: ";
cin>>n;
for(int i=0; i<=n; i++) {
for(int c = 0; c <= (n-i-2); c++) {
cout<<" ";
}
for(int c =0; c< i; c++) {
cout<< fact(i)/(fact(c)*fact(i-c));
}
cout<< endl;
}
return 0;
}Expected Output
1 1 1 1 2 1 1 3 3 1
Explanation of the Program
- Pascal's Triangle is a triangular array of binomial coefficients. Every number in the triangle can be mathematically calculated using the combinations formula (nCr).
- Note on the provided code: The
factfunction contains a logical bug. The loop condition isi < xinstead ofi <= x. This calculates the factorial incorrectly for larger numbers, causing the triangle values to break!
Complexity
Time Complexity
O(n^3) - Nested loops calling a factorial loop.
Space Complexity
O(1)
Common Mistakes
- Writing the factorial loop as
i < xinstead ofi <= x. For example, calculating 3! (which is 3 * 2 * 1 = 6) with<will stop at 2, returning 2 * 1 = 2.
