1
2
3
4
5
6
7
8
9
10
class Solution {
    public int trailingZeroes(int n) {
        int ans = 0, currFactor = 5;
        while (n / currFactor > 0) {
            ans += n / currFactor;
            currFactor *= 5;
        }
        return ans;
    }
}

首先trailing 0的出现是因为有10. 那有多少个10? 凑成10只能是2和5. 于是我们需要知道(2, 5)这种pair有多少. 从1到n的阶乘, 2的个数一定大于5. 对于包含至少1个2的数字, 是每两个数会出现一次, 至少一个5的数字是每5个数出现1个. 只有一个2的数字能把只有一个5的数字都配对. 至少出现两个2的数字是每4个数字出现一个, 至少两个5的数字是每25个数字出现一次. 因此只出现两个2的数字都能和只出现两个5的数字配对. 以此类推.

我们首先查至少包含一个5的数字有多少个, 那就是n / 5个, 因为是每5个出现一个这样的. 其次我们看至少包含两个5的数字有多少个. 是n / 25, 但需要注意的是这些至少包含两个5的数字的第一个5我们之前算过, 因此我们这里只算上第二个5的个数, 有些数字是可能刚好两个5, 有些数字可能还有5, 不要急, 我们继续算. 之后我们算3个5的情况, 也就是每125个数字出现一个, 于是我们算n / 125. 这样以此类推. 等到n / 某个5的次方等于0, 所有的5就都算上了.

时间复杂度: O(logn) log以5为底n的对数. 因为我们是指数增加, 从5到25然后125…, 直到数字大于n.
空间复杂度: O(1)