Medium

题目描述

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

注意 n! = n * (n - 1) * (n - 2) * ... * 3 * 2 * 1。

示例 1：

输入：n = 3
输出：0
解释：3! = 6，没有尾随零。

示例 2：

输入：n = 5
输出：1
解释：5! = 120，有一个尾随零。

示例 3：

输入：n = 0
输出：0

约束条件：

  • 0 <= n <= 10^4

进阶： 你能写出一个在对数时间复杂度内工作的解决方案吗？

解题思路

解题思路

核心观察： 尾随零是由因子10产生的，而10 = 2 × 5。在阶乘中，因子2的数量总是比因子5多，所以我们只需要计算因子5的个数。

分析过程：

  1. 暴力解法思路： 计算n!的值然后数尾随零的个数，但这会导致整数溢出问题。

  2. 数学优化：

    • 每个5的倍数贡献1个因子5
    • 每个25的倍数额外贡献1个因子5（因为25 = 5²）
    • 每个125的倍数再额外贡献1个因子5（因为125 = 5³）
    • 以此类推…

  3. 计算公式：

    结果 = floor(n/5) + floor(n/25) + floor(n/125) + ...

最优解法： 使用循环不断除以5，累加每次的商，直到商为0。这样可以在O(log n)时间内解决问题。

代码实现

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

class Solution:
    def trailingZeroes(self, n: int) -> int:
        count = 0
        while n >= 5:
            n //= 5
            count += n
        return count

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

var trailingZeroes = function(n) {
    let count = 0;
    while (n >= 5) {
        n = Math.floor(n / 5);
        count += n;
    }
    return count;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型大小说明
时间复杂度O(log n)每次循环n除以5，最多循环log₅(n)次
空间复杂度O(1)只使用常数额外空间

相关题目