Trailing Zeros in Factorial

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

n = 5
n! = 120 
Number of trailing zeros = 1
So, return 1

思路:

一个数里有多少0是由这个数的prime factor含多少个2和5的pair决定的，比如
5! = 120，有一个0，因为1 x 2 x 3 x 4 x 5有一个2和5的pair
10! = 1×2×3×4×5×6×7×8×9×10 (= 2 x 5) = 3628800，有两个2和5的pair
20! = 1×2×3×4×5×6×7×8×9×10×11×12×13×14×15×16×17×18×19×20 =  2,432,902,008,176,640,000，有4个0，
因为他有(2 x 5) x 10 (=2 x 5) x 15 (1 x 5) x 20 (2 x 2 x 5)，把20的2借一个给15，就组成了4个2x5的pair。
我们可以发现有5总能找到和他能匹配的2，所以只要数有几个5的prime factor就可以。

Solution:

Time: O(log5(A))
Space: O(1)

public class Solution {
    public int trailingZeroes(int A) {
        int count = 0;
        int i = 1;
        while (A >= Math.pow(5, i)) {
            count += A / Math.pow(5, i);
            i ++;
        }
        return count;
    }
}