Trailing Zeroes of n!

• Find the number of trailing zeroes in 122! ? 

That's a big number right? The solution is pretty simple. Ask yourself when does any multiplication results in a trailing zero? The answer is (2x5) = 10, leaves one zero behind. The factorial of 122 is a multiplication which you already know. The expansion is,

98750442008336013624115798714482080125644041369

78359605958470050267671457205014364903379642774

50422940710230505796264047365129395968426948958

21378210620013388054747214795243520000000000000

000000000000000

So, we have to find the number of multiples of 5 from the expansion and they are 5 10 15 20 25 30 35 40 45 50 55 60 65 70 75 80 85 90 95 100 105 110 115 120.
So there are 24 multiples of 5.

then again, 25= 5 x 5, which has another extra factor of  5 to count. So how many multiples of 25 from 1 to 122?
(122 / 25) = 4 (taking the only integer)

So, add that 4 to the earlier count. 24 + 4 = 28, so we have 28 trailing zero in 122!

Let's take a number even larger than 122. How about 1001!  ?
 
This time we have to check for multiples of 5, 25 and also 125 ( has extra two factor of 5 ),  625 ( has extra four factors of 5 )

easy calculation: ( 1001 ÷ 5 ) + ( 1001 ÷ 25 ) +  ( 1001 ÷ 125 ) + ( 1001 ÷ 625 )= 200+40+8+1 = 249
So 1001! has 249 trailing zeroes.

This shows a pattern: divide N by powers of 5 until the divisior is greater than N.
and this is a special case of de Polignac's formula .

• related problem: http://www.spoj.com/problems/FCTRL/