Factorial Trailing Zeroes

Given an integer n, return the number of trailing zeroes in n!.

Note: Your solution should be in logarithmic time complexity.

I was thinking about using recursion, then I had some problem dealing with extra zeros in cases such as n = 15...

So, I googled, and here comes my favorite Wikipedia:

The number of trailing zeros in the decimal representation of n!, the factorial of a non-negative integer n, is simply the multiplicity of the prime factor 5 in n!. This can be determined with this special case of de Polignac's formula:^[1]

where k must be chosen such that

and  denotes the floor function applied to a. For n = 0, 1, 2, ... this is

0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 6, ... (sequence A027868 in OEIS).

For example, 5³ > 32, and therefore 32! = 263130836933693530167218012160000000 ends in

zeros. If n < 5, the inequality is satisfied by k = 0; in that case the sum is empty, giving the answer 0.

The formula actually counts the number of factors 5 in n!, but since there are at least as many factors 2, this is equivalent to the number of factors 10, each of which gives one more trailing zero.

It is as easy as you can imagine.

Math, ha!

Update: 2015 - 03 - 01

public int trailingZeroes(int n) {
       if (n < 5)
            return 0;
        int zeros = 0;
        int k = 1;
        while (n >= Math.pow(5, k)) {
            zeros += n / Math.pow(5, k);
            k++;
        }
        return zeros;
    }

The reason is that it looses precision after certain positions. The following code will not gives us the correct answer for very large n. Use the above code.

public class TrailingZeros {
    public int trailingZeroes(int n) {
        if (n < 5)
            return 0;
        int zeros = 0;
        int five = 5;
        while (n >= five) {
            zeros += n / five;
            five *= 5;
        }
        return zeros;
    }
}

Update: 2015 - 01 -15

I realize that the above code will exceed time limit, but I couldn't figure the reason.

public int trailingZeroes(int n) {
        if (n < 5)
            return 0;
        if (n == 5)
            return 1;
        int k = 0;
        while (Math.pow(5, k) <= n)
            k++;
        k--;
        int zeros = 0;
        while (k > 0) {
            zeros += n / Math.pow(5, k);
            k--;
        }
        return zeros;
    }