Trailing Zeros

Problem

Write an algorithm which computes the number of trailing zeros in n factorial.

Example

11! = 39916800, so the out should be 2.

Solution

Trailing zeros depends on how many 2 and 5 in the factors, and there are always more 2 than 5, so we only need to count how many 5s, every 5 will result in one 0.

How to count 5?

The example 11! = 11 x 10 x ... x 5 x 4 x 3 x 2 x 1, only 10 and 5 have 5 in factors, so the result is 2.

Another example: 101! = 101 x 100 x 99 x ... x 1, 100, 95, 90 ... 15, 10, 5 has one 5, and 100, 75, 50, 25 has another 5. The easy way to compute the first 5 is 101 / 5 = 20, then to compute the second 5, we can "shrink" the numbers by 5 to 20, 15, 10, 5, if they still have 5 in factors we count another one, so 101 / 5 / 5 = 4. So the overall is:

while (n > 0) {
  cnt += n / 5;
  n /= 5;
}