Thursday, 30 May 2013

print only one line in a pascal's triangle

time complexity:O(n)

We know that ith entry in a line number line is Binomial Coefficient C(line, i) and all lines start with value 1. The idea is to calculate C(line, i) using C(line, i-1). It can be calculated in O(1) time using the following.
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

Program:
#include<stdio.h>
int main(void)
{
int t;
scanf("%d",&t);
while(t--)
{
int n,i,c;
scanf("%d",&n);
c=1;
for(i=1;i<=n+1;i++)
{
printf("%d ",c);
c=c*(n-i+1)/i;
}
printf("\n");
}
return 0;
}

No comments:

Post a Comment