Counting trailing zeros in N!

You are given a number N which will be large (within limits of machine representation of long integer)
You need to find the total trailing zeros in N! (factorial)

Eg,
N = 6
N! = 720
Count = 1 (trailing means to the end)

Solution :

This problem is straight forward. N! = 1 * 2 * 3 * 4 * 5 * .... * N. If we count all 5's in this product, then that many trailing zeros are there. This is because a 5 is countered by 2 to produce a zero. Additionally, there are more 2's than 5's so counting 5's gives the right answer. The following pseudo-code does that:

count = 0
i = 5
while i <= n
  j = i
  while j%5 == 0
    j = j/5
    count += 1
  i += 5

return count

This algorithm takes n/5 outer loop iterations and is bounded by log n [base=5] inner loop iterations, hence it takes O(n log n) time. We can clearly do better than this.

Actually, we can solve this problem in O(log n) time. For a given i the term i/5 gives total number of 5's that come before it. For ex. 17/5 is 3, there are 3 numbers that contain fives which are less than 17 i.e. 5, 10, 15. So we count number of 5, then number of 25, then so on.

count = 0
d = r = 1
while r > 0
  d *= 5
  r = [n/d] // [x] is greatest integer less than x
  count += r
return count

This algorithm runs in O(log n) time and an asymptotic improvement on the previous algorithm.

Acknowledgments :
http://n1b-algo.blogspot.com/2009/01/count-trailing-zeros-in-n-factorial.html