原文链接: https://leetcode-cn.com/problems/preimage-size-of-factorial-zeroes-function

英文原文

Let f(x) be the number of zeroes at the end of x!. Recall that x! = 1 * 2 * 3 * ... * x and by convention, 0! = 1.

• For example, f(3) = 0 because 3! = 6 has no zeroes at the end, while f(11) = 2 because 11! = 39916800 has two zeroes at the end.

Given an integer k, return the number of non-negative integers x have the property that f(x) = k.

 

Example 1:

Input: k = 0
Output: 5
Explanation: 0!, 1!, 2!, 3!, and 4! end with k = 0 zeroes.

Example 2:

Input: k = 5
Output: 0
Explanation: There is no x such that x! ends in k = 5 zeroes.

Example 3:

Input: k = 3
Output: 5

 

Constraints:

• 0 <= k <= 109

中文题目

 f(x) 是 x! 末尾是 0 的数量。（回想一下 x! = 1 * 2 * 3 * ... * x，且 0! = 1 ）

例如， f(3) = 0 ，因为 3! = 6 的末尾没有 0 ；而 f(11) = 2 ，因为 11!= 39916800 末端有 2 个 0 。给定 K，找出多少个非负整数 x ，能满足 f(x) = K 。

 

示例 1：

输入：K = 0
输出：5
解释：0!, 1!, 2!, 3!, and 4! 均符合 K = 0 的条件。

示例 2：

输入：K = 5
输出：0
解释：没有匹配到这样的 x!，符合 K = 5 的条件。

 

提示：

• K 是范围在 [0, 10^9] 的整数。

通过代码

官方题解

方法一：二分查找【通过】

思路和算法

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

zeta(x) 就是 x 除以 5 的次数之和，即 zeta(x) 等于 $\lfloor \frac{x}{5^1} \rfloor + \lfloor \frac{x}{5^2} \rfloor + \lfloor \frac{x}{5^3} \rfloor + \lfloor \frac{x}{5^4} \rfloor + \cdots$`。

可以看出，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 个。

[solution1-Java]
class Solution {
    public int preimageSizeFZF(long K) {
        long lo = K, hi = 10*K + 1;
        while (lo < hi) {
            long mi = lo + (hi - lo) / 2;
            long zmi = zeta(mi);
            if (zmi == K) return 5;
            else if (zmi < K) lo = mi + 1;
            else hi = mi;
        }
        return 0;
    }

    public long zeta(long x) {
        if (x == 0) return 0;
        return x/5 + zeta(x/5);
    }
}

[solution1-Python]
class Solution(object):
    def preimageSizeFZF(self, K):
        def zeta(x):
            return x/5 + zeta(x/5) if x > 0 else 0

        lo, hi = K, 10*K + 1
        while lo < hi:
            mi = (lo + hi) / 2
            zmi = zeta(mi)
            if zmi == K: return 5
            elif zmi < K: lo = mi + 1
            else: hi = mi

        return 0

复杂度分析

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

• 空间复杂度：$O(\log K)$，zeta 递归调用栈的大小。

统计信息

通过次数	提交次数	AC比率
5391	13708	39.3%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言

相似题目

题目	难度
阶乘后的零	中等