阶乘后的零
难度:
标签:
题目描述
给定一个整数 n ，返回 n! 结果中尾随零的数量。
提示 n! = n * (n - 1) * (n - 2) * ... * 3 * 2 * 1
示例 1：
输入：n = 3 输出：0 解释：3! = 6 ，不含尾随 0
示例 2：
输入：n = 5 输出：1 解释：5! = 120 ，有一个尾随 0
示例 3：
输入：n = 0 输出：0
提示：
0 <= n <= 104
进阶：你可以设计并实现对数时间复杂度的算法来解决此问题吗？
代码结果
运行时间: 20 ms, 内存: 16.1 MB
/*
题目思路：
计算n!中尾随零的数量可以通过计算因子5的个数来完成。
利用Stream.iterate生成从5开始的数列，每次迭代乘以5，直到数列的值大于n。然后对每个元素n/k取整并求和。
*/
import java.util.stream.Stream;
public class Solution {
public int trailingZeroes(int n) {
return Stream.iterate(5, k -> k <= n, k -> k * 5)
.mapToInt(k -> n / k)
.sum();
}
}
解释
方法:
该题解利用了数学分析的方法来计算阶乘结果中尾随零的数量。观察可知，只有当出现 2 和 5 相乘时才会产生尾随零。而 2 的数量远大于 5 的数量，因此 5 的个数决定了尾随零的数量。通过计算 n 中包含的 5 的因子数，即可得到尾随零的数量。具体做法是通过循环不断地将 n 除以 5，并累加商，直到 n 为 0 为止。
时间复杂度:
O(log n)
空间复杂度:
O(1)
代码细节讲解
🦆
为什么尾随零的数量是由因子5的数量决定而不是因子2的数量？
▷🦆
在循环中每次将n除以5，这种方法为何能准确计算出包含的因子5的总数？
▷🦆
是否存在一种情况下，简单地累加n除以5的结果会导致计算过或计算少尾随零的数量？
▷相关问题
数字 1 的个数
给定一个整数 n，计算所有小于等于 n 的非负整数中数字 1 出现的个数。
示例 1：
输入：n = 13 输出：6
示例 2：
输入：n = 0 输出：0
提示：
0 <= n <= 109
阶乘函数后 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 <= 109