Calculating large factorials mod 10^9+7

With reference to the following editorial : https://www.hackerearth.com/problem/algorithm/problem4-1/editorial/

Could anyone just explain the editorial as what does author is actually doing when he is saying hardcoring the factorial . Any help would be appreciated.

Thanks in advance.

Hi @japoorv
As far as I could understand, the editorial asks you to precompute all the factorials till the largest n possible using some other program in your system locally.Now using this output, consider only those which are multiples of 10^6 i.e 0!, (10^6)!, (2 * 10^6)!..till (n/10^6) * 10^6! and store these numbers in a array.There will be exactly n/(10^6) of these numbers. So you will now have an array in which arr[i] equals factorial of i * 10^6. Now suppose you want to calculate factorial of some number.Lets say 1993456.Now since this number lies between 10^6 and 2*10^6 you can get factorial of 10^6 in O(1) from the array . Now whats left is multiplying all the numbers from 1000001 to 1993456 to this number which can be done in 10^6 operations.With the same logic , it can be said that factorial for any number can now be calculated in at max 10^6 operations.Hope it helps:)

3 Likes

Hi. I wrote the editorial for this problem.

The explanation of @nilotpal9797 is correct. What I used was storing the value of the factorial at every multiples of 10^7, but one can alternatively store multiples of 10^6, 10^5 or even 10^4 since it is possible to create an array of such size.

It seems that the explanation wasn’t quite clear, so I updated the editorial. Thanks for posting this doubt!

1 Like

On a side note, who wrote the editorial for Replace and Potential ? They were very good questions but I cannot figure out the strategies from the editorial. If you wrote them also, can you please update the editorial to be more beginner friendly.? Thnx.