FCTRL2 - Small factorials:
You are asked to calculate factorials of some small positive integers.
Input
An integer t, 1<=t<=100, denoting the number of testcases,
followed by t lines, each containing a single integer n,
1<=n<=100.
Output
For each integer n given at input, display a line with the value of n!
Example
Sample input:
4 1 2 5 3Sample output:
1 2 120 6
The link to this problem is:
http://www.spoj.com/problems/FCTRL2/
#include <stdio.h>
int main(void) {
long long i,j,k,n,sum,a[200],carry,more,t,r,ii;
scanf("%lld",&t);
for( ii=0;ii<t;ii++)
{
scanf("%lld",&n);
for(i=0;i<=200;i++)
a[i]=1;
k=0;
carry=0;
for(i=1;i<=n;i++)
{
for(j=0;j<=k;j++)
{
a[j]=a[j]*i+carry;
carry=a[j]/10;
a[j]=a[j]%10;
}
while(carry>0)
{
k++;
r=carry%10;
carry=carry/10;
a[k]=r;
}
}
for(i=k;i>=0;i--)
{
printf("%lld",a[i]);
}
if(ii!=t-1)
printf("\n");
}
return 0;
}
Input:1
5
Output:120
To understand this properly first we need to know how to multiply two numbers using an array.
Suppose the numbers can be 12 and 97 we need to multiply using an array.First take 1 in array and multiply with 12
Initially the array must contain '1' at the 0th index and remaining
index values are considered as zeros and initial carry also '0'.
Initially the array contains
index 1 0
0 1*12 <= array values
=> 0 12
Here now '2' should be at '0' location 1 is carry add to next index value
index 1 0
0*12+ 1 2
At every index multiply the array value with 97 and add the carry value
to the array value and later put the arrayvalue%10 there and carry now
becomes arrayvalue/10
Multiply with 97
index 3 2 1 0
0 0 1 2*97 <=arrayvalues1 194
0 0 1*97+19 4
116 4
0 0*97+11 6 4
0*97+1 1 6 4
1 1 6 4
Now this logic is only applied for factorial in which each array value is multiplied by number in factorial multiplication in the above code.
These two logics only carry and addition of index values is applied in for loop logic.
So know we got the multiplication of two numbers using arrays now what we must implement for the factorial suppose the number is 5!
So we need to multiply as 5*4*3*2*1.
So initially array is multiplied between initial array and 5.
Then later the current array is multiplied by 4 and so on until we multiply 3 ,2, 1, on the array values.
Now while printing the output print the value from highest index to the 0th index so this will be result of your factorial.
I appreciated your work very thanks sviluppo siti web Milano
ReplyDelete