1 题目描述

2 解题思路

令 zeta(x) 为 x! 末尾零的个数。如果 x! 可以分解为素数的乘积，如的形式，那么 x! 末尾零的个数为 min(a, b) = b。

zeta(x) 就是 x 除以 5 的次数之和，即 zeta(x) 等于

可以看出，zeta(x) 是一个单调递增函数，因此可以使用二分查找求解。

使用二分查找找出满足 zeta(x) = K 的最大 x 和最小 x

由于一定存在 zeta(5a-1) < zeta(5a) = zeta(5a+1) = zeta(5a+2) = zeta(5a+3) = zeta(5a+4) < zeta(5a+5)，即如果存在某个 x 使得 zeta(x) = K，那么一定存在连续 5 个数的阶乘末尾零的个数都为 K；如果不存在这样的 x，那么阶乘末尾零的个数为 K 的数字只有 0 个。

class Solution(object):def preimageSizeFZF(self, K):def zeta(x):if(x==0):return 0else:return x//5 + zeta(x//5) lo, hi = 4*K, 5*K + 1while lo < hi:mi = (lo + hi) // 2zmi = zeta(mi)if zmi == K: return 5elif zmi < K: lo = mi + 1else: hi = mireturn 0 #最终没有找到这个数

接下来解释一下这边二分查找的时候的左边界和右边界是怎么找的：

我们可以得到

即x≥4k

即x≤5k

复杂度分析

时间复杂度：，二分查找的复杂度为 O(log K)，其中每一步计算 zeta 的复杂度也为 O(logK)。

空间复杂度：O(logK)，zeta 递归调用栈的大小。

总结

以上是生活随笔为你收集整理的文巾解题 793. 阶乘函数后 K 个零的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。