 # CMC303 - Editorial

Newton Per Metre Square

Author: artha6391
Tester: anushka_nagar
Editorialist: anushka_nagar

SIMPLE-EASY

# PROBLEM:

The problem describes process of forming a pascal’s triangle. You have to output pascal’s triangle up to Nth row.

# QUICK EXPLANATION:

Every entry in a line is value of a Binomial Coefficient.

Hence, we know that the value of ith entry in line number line is C(line, i) and all lines start with value 1.

So C(line, i) can be calculated from C(line, i-1) in O(1) time as follows

C(line, i) = C(line, i-1) * (line - i + 1) / i

# EXPLANATION:

Binomial Coefficient C(n,k) is given as n! / k! (n-k)!

Hence,

C(line, i) = line! / ( (line-i)! * i! )

C(line, i-1) = line! / ( (line - i + 1)! * (i-1)! )

We can derive following expression from above two expressions.

C(line, i) = C(line, i-1) * (line - i + 1) / i

So C(line, i) can be calculated from C(line, i-1) in O(1) time

# SOLUTIONS:

Setter's Solution
``````#include <bits/stdc++.h>

using namespace std;
void printPascal(int n)
{
for (int line = 1; line <= n; line++){
for (int i = 1; i <= line; i++){
cout<< C<<" ";
C = C * (line - i) / i;
}
cout<<"\n";
}
}

int main()
{
int t;
cin>>t;
while(t--){
int n;
cin>>n;
printPascal(n);
cout<<endl;
}
return 0;
}
``````
Tester's Solution
``````#include <bits/stdc++.h>

using namespace std;
void printPascal(int n)
{
for (int line = 1; line <= n; line++){
for (int i = 1; i <= line; i++){
cout<< C<<" ";
C = C * (line - i) / i;
}
cout<<"\n";
}
}

int main()
{
int t;
cin>>t;
while(t--){
int n;
cin>>n;
printPascal(n);
cout<<endl;
}
return 0;
}
``````
Editorialist's Solution
``````#include <bits/stdc++.h>

using namespace std;
void printPascal(int n)
{
for (int line = 1; line <= n; line++){
for (int i = 1; i <= line; i++){
cout<< C<<" ";
C = C * (line - i) / i;
}
cout<<"\n";
}
}

int main()
{
int t;
cin>>t;
while(t--){
int n;
cin>>n;
printPascal(n);
cout<<endl;
}
return 0;
}
``````