Trailing Zeros
Given an integer ’n’, we are supposed to find out the number of trailing zeros in ‘n!’ .
One obvious way is to calculate n! and count the number of trailing zeros.
But this approach is not efficient as the value of n! can exceed the limit of unsigned long long for 1<n<10⁹ . Hence, we try to device some other method to count the number of trailing zeros in n! without actually having to calculate n!.
Take any number. Let’s say ‘7’.
Let us multiple it by ‘2’.
7*2 = 14
Does multiplying ‘7’ by ‘2’, give us an answer with a trailing a zero? No. There are no trailing zeros in ‘14’.
Let us multiply ‘7’ by ‘10’.
7*10 = 70
We get a trailing zero! Clearly, any integer has a trailing zero if it has ‘10’ as one of it’s factors.
Now, ‘10’ = ‘2’ * ‘5’.
Next, let us multiply ‘70’ by ‘2’.
70 * 2 = 140
Still the same number of trailing zeros = 1.
Let us multiply ‘70’ by ‘5’.
70 * 5 = 350
Still the same number of zeros = 1.
Lets us multiply ‘70’ by ‘2 * 5’.
70 * 2 * 5 = 700
The number of trailing zeros increased by one.
Let us multiply ‘700’ by ‘2 * 5’
700 * 2 * 5 = 7000
Another trailing zero added.
Clearly, to count the number of trailing zeros in any number, I need to account for number of pairs of multiple of ‘5’ and multiples of ‘2’ .
Consider 10!
10! = 10 * 9 * 8 * 7 * 6* 5 * 4 * 3 * 2 * 1 = 3628800
In the expansion of 10!, we can see that there are many more multiples of 2 (10,8,6,4…) than there are of 5 (10,5).
It means that if I count all the numbers with ‘5’ as a factor, I will always have enough even numbers to pair them with. Hence, I only need to find out how many numbers, with ‘5’ as a factor, are there between 1 and ’n’.
From 1 to 10, there two number (5 and 10) with ‘5’ as a factor, hence, 10! has two trailing zeros.
The number of multiples of ‘5’ in the factorial of any number can simply be calculated by dividing that number by ‘5’.
10/5 =2 = number of trailing zeros in 10!
Consider 15!
15! = 435456000 , three trailing zeros.
15/5 = 3 = number of trailing zeros.
Consider 25!
25/5 = 5
Hence there should be 5 trailing zeros in the factorial of 25.
But, 25! = 15511210043330985984000000
i.e. six trailing zeros .
What went wrong?
The expansion of 25! = 25 * 24 * 23 * 22 * 21 * 20 * 19…
How many multiples of ‘5’ are there in this expansion?
5, 10, 15, 20, 25.
5 = 5* 1
10 = 5 * 2
15 = 5 * 3
20 = 5 * 4
25 = 5 * 5
There is an additional factor of ‘5’ in ‘25’ which our formula (n/5) does not account for.
Hence, to count all the ‘5’s, we first divide n by 5, save the result. And then keep dividing the result by 5 (and adding it to previous result)as long as it is greater than 1.
25/5 = 5 , zeros =5
5/5 = 1, zeros = 5+1 = 6
trailing_zeros =0;
while(n>1){
trailing_zeros +=n/5;
n=n/5;
}
