Pascal's Triangle - Sum of Selected Coefficients

You must have heard of Pascal’s triangle. In this programming assignment, your program is required to compute the sum of a given set of elements of  the Triangle.  Most importantly, your program should have a recursive function to calculate the values in the triangle.

As you know, the values in the Pascal’s Triangle are called Binomial Coefficients.   At the top tip of the arrangement is number 1, which makes up the zeroth row. The first row contains two 1's . In general, in each row, the first and the last numbers are 1.  To find any number in the i th row, add the two numbers immediately above it in (i-1)th row, as shown in the diagram below.

NPUT & OUTPUT:

The input consists of multiple lines. The first line contains a number n which indicates that the number of rows in the Pascal’s triangle will be n+1 (Note that rows of Pascal’s triangle are indexed starting with 0 at the top and the elements in a row are also indexed starting with a 0).

The second line contains a number m which indicates the number of transactions to be performed on the Pascal’s triangle. Each transaction is given in a separate line.  A transaction is a space separated list of integers. The first integer in each list indicates the row number, say R, and the rest of the integers in the list indicate the indices of values in row R. For each transaction, you have to compute the sum of given coefficients in the given row R.

Example: Input will be given in the following format:

5

3

3 1 2

5 1 1 1 4

4 2 3 2

• Here, the First line contains number 5. So there will be 6 rows in the corresponding Pascal’s triangle as shown below:

• The Second line of the input indicates that we must perform 3 transactions.
• The Third line contains a space separated list  i.e, 3 1 2  - the output for this line should be the sum of 1st coefficient and 2nd coefficient in the 3rd row of the triangle (thus output for this transaction should be 3C1+3C2 = 6).
• Similarly we can compute the output for the other two transactions listed in lines 4 and 5.

The output must be a space separated sequence of integers terminated by a new-line. For each transaction there must be 1 integer in the output list that corresponds to the sum of specified coefficients in that transaction. If the transaction has an invalid input, i.e, when any of the indices are out of bound or the row number is greater than n, then the output must be a -1.

Thus output for the given input would, thus, be:

6 20 16
Sample Input :

6

4

7 1 2 2 3

5 0 1 1 4

4 2 3 2

6 4 5 3 2 1

Sample Output :

-1 16 16 62

Solution -----------

#include<stdlib.h>
#include<stdio.h>
#include<string.h>
long int fact(int);
int main()
{int n,t,r,i,k,j,cd,l,a[100]={0};long int num,den1,den2,ans,sum;char c;
scanf("%d",&n);
scanf("%d",&t);

for(i=1;i<=t;i++)
{
scanf("%d",&r);
j=0;sum=0.0;
while(1)
{c='a' ;
scanf("%d%c",&a[j],&c);

if(c=='\n'||c=='a')
break;

else 
j++;

}
cd=0;
for(l=0;l<=j;l++)
{
if(a[l]>r)
cd++;}
if(cd==0)
{for(k=0;k<=j;k++)
{if(a[k]<r)
{num=fact(r);
den1=fact(r-a[k]);
if(a[k]!=0)den2=fact(a[k]);
else
den2=1;
ans=den1*den2;
ans=num/ans;
sum=sum+ans;}
else if(a[k]==r)
sum=1+sum;

}
}
else
{
r=n+1;}


if(r>n)
printf("-1 ");

else
printf("%ld ",sum);

}
return 0;
}
long int fact(int n)
{
if(n==1)
return 1;
else
return (n*fact(n-1));


}