Hey there,
To find the number of trailing zeroes in a factorial, we need to find the power of twos and fives in the prime factorization of the factorial.
Like in 5!, expansion of it is,
5!=5 x 4 x 3 x 2 x 1 = 2^3 x 3^1 x 5^1,
and by finding minimum number out of the number of 2s and the number of 5s, which will always be number 5s as we will always have the extra number of 2s, we can find out the number of trailing 0s in factorial.
Now how to find the power of 5 or any prime number, we will follow the following procedure.
Let's find the power of 5 in 200!
200! = 1x2x3x...x199x200
as we need to find the power of 5, we will neglect other terms and observe the numbers divisible by 5
200! = 5x10x15x...x195x200 x others
taking out the powers of 5 from all the numbers,
200! = 5^(200/5) x (1x2x3x...x39x40) x others
200! = 5^(40) x (1x2x3x...x39x40) x others
repeating the process in the inner bracket,
200! = 5^(40) x (5x10x15x...x35x40) x others
200! = 5^(40) x 5^(40/5) x (1x2x3x...x7x8) x others
200! = 5^(40) x 5^(8) x (5) x others
The power of 5 in 200! = 40 + 8 + 1 = 49
If we observe, we see that at each iteration we are getting the number of powers of 5.
Like, power of 5 in n! = floor(n/5) + floor(n/(5^2)) + floor(n/(5^3)) + ... till we get a power of 5 greater than n after which all terms equals to 0.
We can generalize this in following way:
Power of k in n! = floor(n/k) + floor(n/(k^2)) + floor(n/(k^3)) +...
We can get the number of terms by :
Terms t= log base k of n = log(n)/log(k)
In the same way, we can find power of any prime number or any other number(with prime factorization and then following the process) using this method.
An application of it is in the problem: https://codeforces.me/contest/633/problem/B
In this question, we need to find the numbers whose factorial has the given number of zeroes 'm'.
Easy and Dumb way to do this is by running a loop till we find the solution and as the value of m is small, we will even find the value in a reasonable time. But an optimized way is to perform binary search to the number of zeroes within the range.
The Lower limit of zeroes is 1 which is in 5!. The Upper limit is 100,000 which after a hit and trial way we find that to be in 400,005!.
As the number of zeroes will increase on every fifth number, we will deal with the limit in that way too.
The left limit of factorial is 5 as it corresponds to 1 zero and right limit is 400,005 as it corresponds to 100,000!.
So dividing the limits by 5 and working in that way, left limit l = 1 and right limit r = 400,005/5 = 80,001.
We will make a function which returns the number of zeroes of the passed argument using above method, as we will frequently need the function.
Binary search works in case of sorted numbers and as in our case as the number increases the number of trailing zeroes in the factorial increases, we can apply binary search.
Now the way binary search works is:
Comparing the mid value of both limits. mid=(l+r)/2. If the required value is the mid value then the loop breaks. And we get the value.
If the mid value is greater than required,the mid value becomes the new right limit as the required one will not be in the second half.
Similarly if mid value is less than required, the mid value becomes the new left limit.
And if the left limit will become greater than the right limit, we will break and no number is there with required zeroes.
But in our case we need to compare the zeroes of left limit and right limit with the required zeroes 'm'.
And we are dealing with 5 times the left or right limits mid values number of zeroes.
So our algorithm goes this way:
Let's take the input m = 24999
l=1 , r=80,001 , so mid=(l+r)/2 = 40,001
Now zeroes of 5*l = 1 , zeroes of 5*r = 100,000 and zeroes of 5*mid = 49999
As m is less than mid value, mid value becomes new right limit.
l=1, r=40,001 , so mid= 20,000
Zeroes of 5*mid = 24999 which is the required number so we break the loop.
In this way we can solve the problem in the best way.
P.S: this is my first blog, ignore the mistakes.
