|
题目难度: 简单 原题链接 题目描述 设计一个算法，算出 n 阶乘有多少个尾随零。 示例 1:输入: 3输出: 0解释: 3! = 6, 尾数中没有零。示例 2:输入: 5输出: 1解释: 5! = 120, 尾数中有 1 个零.说明你算法的时间复杂度应为 O(log n) 。题目思考哪些数字会贡献尾数 0?解决方案思路分析题目, 阶乘的每个尾数 0 都是由因子 5 和因子 2 相乘而得, 而显然因子 2 的数目肯定大于因子 5 的数目 (因为每个偶数都至少贡献 1 个因子 2, 而只有 5 的倍数才贡献至少 1 个因子 5)所以只需要统计 1~n 的所有数中有多少个因子 5 即可, 每个因子 5 都会贡献出 1 个尾数 0而哪些数字具有因子 5 呢? 我们可以枚举一些数字来寻找规律:可以被 5 整除但不能被 25 整除的数, 例如 5,10,15,...有一个因子 5可以被 25 整除但不能被 125 整除的数, 例如 25,50,75,...有两个因子 5依此类推...这样我们可以使用一个变量 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 |