# 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:&#x20;

**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\
&#x20;     a) Find value of res\[i] \* x + carry. Let this value be prod.\
&#x20;     b) Update res\[i] by storing last digit of prod in it.\
&#x20;     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**

```cpp
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];
    }
}
```
