FCTRL2 - Small factorials Editorial-Solution - UCS - Unleash-Coding-Skills

Sunday, 25 March 2018

FCTRL2 - Small factorials Editorial-Solution - UCS

In this we have the solution to

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
3
Sample 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 <=arrayvalues
                                                                   1                             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.

 

Happy Coding........

Feel Free to add comment..............
 

No comments:

Post a comment