LeetCode-172 阶乘后的零

📝题目

给定一个整数 n，返回 n! 结果尾数中零的数量。 

示例 1:

输入: 3
输出: 0
解释: 3! = 6, 尾数中没有零。

示例 2:

输入: 5
输出: 1
解释: 5! = 120, 尾数中有 1 个零。

说明: 算法的时间复杂度应为 O(log n) 。

📝思路

观察1!, 2!, 3!, 4!, 5!...，可以看出从5!开始尾数有一个零，10!开始尾数有两个零，15!开始尾数有三个零…可以猜测我们的算法将从因子5下手，最开始的想法是return n / 5（不过当然不可能是这种干脆利落的O(1)啦），当从25!开始时，因为25可以拆分成5*5，因此此时是return n / 5 + 1…可以进一步猜测结果与5的幂次有关。更详细的题解戳这里。

📝题解

int trailingZeroes(int n) {
    int fives = 0;
    int five_power = 5;
    while (n / five_power > 0) {
        fives += n / five_power;
        five_power *= 5;
    }
    return fives;
}