What is the time complexity of the solution?

The time complexity is O(log(n)), where n is the upper bound of possible factorial values.

How do we calculate the number of trailing zeroes in x!?

We count how many times x is divisible by powers of 5 (e.g., 5, 25, 125), and sum these counts.

What if there is no integer x such that x! ends with exactly k trailing zeroes?

In such cases, the solution should return 0 as no valid x exists.

How does binary search improve the time complexity here?

Binary search reduces the search space logarithmically, allowing for an efficient solution instead of checking every possible x.

Why are trailing zeroes in factorials determined by factors of 5?

Trailing zeroes in a factorial are formed by pairs of 2 and 5 factors. Since there are more factors of 2 than 5, the number of trailing zeroes is determined by the number of 5s.

#793

Hard

auto_awesome二分·搜索·答案·空间

LeetCode 题解工作台

阶乘函数后 K 个零

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 ，找出返回能满足…

数学二分查找

题目描述

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，找出返回能满足 f(x) = k 的非负整数 x 的数量。

示例 1：

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

示例 2：

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

示例 3:

输入: k = 3
输出: 5

提示:

0 <= k <= 10⁹

lightbulb

解题思路

方法一：二分查找

定义 $f(x)$ 为 $x!$ 末尾零的个数，那么

f(x)= \begin{cases} 0, x=0\\ x/5+f(x/5), x>0 \end{cases}

定义 $g(k)$ 表示 $x!$ 末尾为零的个数为 $k$ 的最小的 $x$ 值，那么题目等价于求解 $g(k+1)-g(k)$ 。

由于 $g(k)$ 是单调递增的，因此可以使用二分查找求解 $g(k)$ 。

同时，由于 $f(x)=x/5+f(x/5) \ge x/5$ ，因此 $f(5k)\ge k$ 。所以，求解 $g(k)$ 时，二分的右边界可以取 $5k$ 。

时间复杂度 $O(log^2k)$ ，其中 $k$ 为题目给定的整数。二分查找 $g(k)$ 的时间复杂度为 $O(logk)$ ，计算 $f(x)$ 的时间复杂度为 $O(logx)$ ，因此总时间复杂度为 $O(log^2k)$ 。

1

2

3

4

5

6

7

8

9

10

11

12

class Solution:
    def preimageSizeFZF(self, k: int) -> int:
        def f(x):
            if x == 0:
                return 0
            return x // 5 + f(x // 5)

        def g(k):
            return bisect_left(range(5 * k), k, key=f)

        return g(k + 1) - g(k)

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Tests the candidate's understanding of binary search in a mathematical context.
question_mark
Assesses problem-solving efficiency through an optimization approach.
question_mark
Evaluates ability to implement mathematical algorithms for large input sizes.

warning

常见陷阱

外企场景

error
Overlooking the fact that trailing zeroes only depend on the factors of 5.
error
Failing to account for the fact that there might be no valid x for large k values.
error
Using brute force or non-optimal solutions instead of binary search to minimize time complexity.

swap_horiz

进阶变体

外企场景

arrow_right_alt
What happens if the problem were to ask for x! to end with exactly k+1 trailing zeroes instead of k?
arrow_right_alt
How would the solution change if factorials had to end with an even number of trailing zeroes?
arrow_right_alt
If k is a very large number, how would we adjust the approach to ensure correctness and efficiency?

help

常见问题

外企场景

继续练习

#754 到达终点数字 #710 黑名单中的随机数 #878 第 N 个神奇数字