172. Factorial Trailing Zeroes

Description

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

Note: Your solution should be in logarithmic time complexity.

Solution

蛮有趣的题目。细细想来，10分解成质数就是2*5，每个0都需要一对2和5来造成：
n! = 2^x * 5^y * … where x and y >= 0
很明显，x >= y，只需计算y即可。
那么5的个数如何计算呢？对于每个k来说，需要计算它由几个5组成。注意，并不是只有5的幂才会出现多个5，像50里面就有两个5！
5=1*5, 10=2*5, 15=3*5, 20=4*5, 25=5*5, 30=6*5 ... , 50=10*5=2*5*5

result = (1到n中被5^1整除的个数) + （1到n中被5^2整除的个数）+ ... + （1到n中被5^m整除的个数）

就可以用递归的思路啦，1到n中被5^1整除的个数即n / 5。

class Solution {
    public int trailingZeroes(int n) {
        int zeroes = 0;
        while (n > 0) {
            n /= 5;
            zeroes += n;
        }
        return zeroes;
    }
}