Count Trailing Zeros in N Factorial

How many trailing zeros does N factorial contain, for ex. 5! = 120 so ans is 1. Propose an algorithm to count trailing zeros. Assume that N! is very large and does not fit into word size of the computer.

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.