题目难度: 简单

原题链接

今天继续更新程序员面试金典系列, 大家在公众号 算法精选 里回复 面试金典 就能看到该系列当前连载的所有文章了, 记得关注哦~

题目描述

设计一个算法，算出 n 阶乘有多少个尾随零。

示例 1:

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

示例  2:

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

说明

• 你算法的时间复杂度应为  O(log n) 。

题目思考

1. 哪些数字会贡献尾数 0?

解决方案

思路

• 分析题目, 阶乘的每个尾数 0 都是由因子 5 和因子 2 相乘而得, 而显然因子 2 的数目肯定大于因子 5 的数目 (因为每个偶数都至少贡献 1 个因子 2, 而只有 5 的倍数才贡献至少 1 个因子 5)
• 所以只需要统计 1~n 的所有数中有多少个因子 5 即可, 每个因子 5 都会贡献出 1 个尾数 0
• 而哪些数字具有因子 5 呢? 我们可以枚举一些数字来寻找规律:
  1. 可以被 5 整除但不能被 25 整除的数, 例如 5,10,15,…有一个因子 5
  2. 可以被 25 整除但不能被 125 整除的数, 例如 25,50,75,…有两个因子 5
  3. 依此类推…
• 这样我们可以使用一个变量 x 代表当前因子, 初始化为 5, 然后每次乘以 5 直到 x>n
• 累加所有的 n//x, 即为 1~n 的因子 5 的总个数, 也即最终要求的结果: 阶乘尾数 0 的个数
• 举个例子, 125 会被整除 3 次, 即 x=5, x=25 和 x=125, 也即代表它有 3 个因子 5

复杂度

• 时间复杂度 O(logN): 时间复杂度是以 5 为底的 n 的对数, 因为只需要循环该对数次
• 空间复杂度 O(1): 只使用了几个常数空间变量

代码

class Solution:
    def trailingZeroes(self, n: int) -> int:
        # x代表当前因子
        x = 5
        res = 0
        while x <= n:
            # 累加当前因子的贡献值
            res += n // x
            x *= 5
        return res

大家可以在下面这些地方找到我~