-
Asked by: Mahima_Kriti on April 7, 2019, 6:34 p.m. Last updated on April 7, 2019, 6:34 p.m.
If you find the factorial of number using first method , integer overflow may occur because in the first method we are first calculating factorial of number, that must be stored in int data type, as factorial of number can be very large so it is not possible to store it in any integer variable.
But in second method, we take mod after every iteration of for loop to avoid overflow.
unsigned long long factorial(int n)
{
const unsigned int M = 1000000007;
unsigned long long f = 1;
for (int i = 1; i <= n; i++)
f = (f*i) % M;
return f;
}
As the value of a%b is always less than b ,hence on taking mod after every multiplication ,value of f is always less than M hence there will never be problem of integer overflow.
This factorial function calculates value of (n! % M) i.e it calculates remainer when n! is divided by M.
See,the reason we use mod is because we can't store a particular value.
For example - we cant store a value such as 1234567891111 in an integer datatype.in such cases we store the value of this number modulo 10^9+7(generally)...So your answer should be 1234567891111%(10^9+7)[in this case]
Now coming to finding factorial ,
consider finding 30!
try analysing the number of digits in that number .. they are way to many to be stored in an integer datatype..
You could argue that we can find the value of 30! first and then take the mod...that would give an incorrect result ..because the value of 30! itself cannot be stored ..
By using the line "f = (f*i) % M; ", we make sure the value of the result is always in the range which can be stored by us.
If you dont get this ,try calculating all the factorial from 1 to 20 and store in integer datatype and check the values...