0172：阶乘后的零（★）

力扣第 172 题

题目

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

提示 n! = n * (n - 1) * (n - 2) * ... * 3 * 2 * 1

示例 1：

输入：n = 3
输出：0
解释：3! = 6 ，不含尾随 0

示例 2：

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

示例 3：

输入：n = 0
输出：0

提示：

• 0 <= n <= 104

进阶：你可以设计并实现对数时间复杂度的算法来解决此问题吗？

相似问题：

• 0233：数字 1 的个数
• 0793：阶乘函数后 K 个零（2100 分）
• 2117：一个区间内所有数乘积的缩写（2476 分）
• 2245：转角路径的乘积中最多能有几个尾随零（2036 分）

分析

数学分析：

• 结尾零的个数等于 n! 的质因数中 (2, 5) 对的个数
• 显然 5 更少，因此结果就等于因子 5 的个数
• 从 1 到 n ，含有 1 个因子 5 的个数是 n // 5，含有 2 个因子 5 的个数是 n // 25，依此类推
• 结果为： $$n // 5 + n // 25 + n // 125 + …$$

解答

1
2
3
4
5
6
7

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

51 ms