3.Extra Long Factorials

Factorial of 100 has 158 digits.(Cannot be stored in long long int ) A simple solution where we use an array to store individual digits of the result.

Solution:

Algorithm: Multiply the digits with the numbers in the array. 1) Initialize carry as 0. 2) Do following for i = 0 to res_size – 1 a) Find value of res[i] * x + carry. Let this value be prod. b) Update res[i] by storing last digit of prod in it. c) Update carry by storing remaining digits in carry. 3) Put all digits of carry in res[] and increase res_size by number of digits in carry. Do this for all numbers from 2 to N

int calcFact(int x, vector<int> &res, int resSize)
{

    int carry = 0;
    for (int i = 0; i < resSize; i++)
    {
        int p = res[i] * x + carry;
        res[i] = p % 10;
        carry = p / 10;
    }
    while (carry > 0)
    {
        int x = carry % 10;
        res[resSize] = x;
        resSize++;
        carry = carry / 10;
    }
    return resSize;
}

void extraLongFactorials(int n)
{

    vector<int> res(158);
    int resSize = 1;
    res[0] = 1;
    for (int i = 2; i <= n; i++)
    {
        resSize = calcFact(i, res, resSize);
    }

    for (int i = resSize - 1; i >= 0; i--)
    {
        cout << res[i];
    }
}