LeetCode 172. 阶乘后的零

LeetCode 172. 阶乘后的零

思路：
每个10只能由 2 * 5 组成，所以统计2与5的个数中最小的个数就是答案。统计5的个数就是统计 5 5^{2 5}3 ...5^{k ，1 + 2 + 3 + ... +k就是5的个数。因为在一个阶乘中，5 5}2 5^{3 ...5}k各贡献了一次，所以5的总次数就是每一种的个数加在一起。

例如 25! = 1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10 * 11 * 12 * 13 * 14 * 15 * 16 * 17 * 18 * 19 * 20 * 21 * 22 * 23 * 24 * 25

这里面5贡献了5次 (5 10 15 20 25)
这里面25贡献了1次 （25）

一共 6 次

代码：

class Solution {
public:
    int trailingZeroes(int n) {
        return n < 5 ? 0 : trailingZeroes(n / 5) + n/5;
    }
};