## Number of zeros in a Factorial

*March 7, 2009 at 1:27 pm* *narinderberi* *
1 comment *

Its an interesting problem at:

http://www.codechef.com/problems/FCTRL/

Advertisements

Entry filed under: Uncategorized.

1.Narinder Beri | March 7, 2009 at 1:38 pmThe logic is that each 2 & 5 results in a 10, and hence a zero in the factorial. Since 2’s frequency is higher than 5, so we do not consider 2 but simply focus on 5.

5! => 1

10! => 2

15! => 3

etc.

So n! will have at least n/5 zeros in it.

The only catch is that with a multiple of 5 like 25, which has 2 5’s hidden in it, an additional zero will show up. Same goes for 100.

So the catch junctions are:

25, 125, 625… Each junction gives an additional zero.

So, considering 25 and its multiples, we get 25, 50, 75,… Each of these gives 1 extra 5 on top of that given by the virtue of being a multiple of 5.

So, considering 125 and its multiples, we get 125, 250, 375,… Each of these gives 1 extra 5 on top of that given by the virtue of being a multiple of 5 and 25.

So, n! has n/5 + n/25 + n/125 + (till n/m becomes zero) … number of zeros in it.