SPOJ : FCTRL2 (Small Factorials)

Small Factorials (FTRL2)

A simple implementation would be:

int fac(int a)
{
    int temp=1;
    for(i=1;i<=a;i++)
        temp=temp*i;
    return temp;
}

This implementation though correct has one serious drawback, it won’t be calculate correct factorials, the answers of which overflow the range of int, even if we take unsigned long long int the range is roughly 4*10^18 and the answer overflows when we are in 30s.

So how do we calculate 100!

For solving, we take an array ans store 1 in the first location, then we successively multiply numbers upto ‘a’, each time storing only one decimal digit at one index, try understanding the following implementation:

#include<stdio.h>
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int num;
        int i,k=0,j,carry=0,arr[1000]={1};
        scanf("%d",&num);
        for(i=1;i<=num;i++)
        {
            for(j=0;j<=k;j++)
             {
                arr[j]=arr[j]*i+carry;
                carry=arr[j]/10;
                arr[j]=arr[j]%10;
             }
             while(carry)
             {
                 k++;
                 arr[k]=carry%10;
                 carry/=10;
             }
         }
         for(i=k;i>=0;i--)
            printf("%d",arr[i]);
        printf("\n");
    }
    return 0;
}