阶乘函数后 K 个零
难度:
标签:
题目描述
代码结果
运行时间: 24 ms, 内存: 16.1 MB
/*
题目思路:
1. 使用与 Java 版本相同的思路,但使用 Java Stream 实现查找过程。
2. 使用 Stream.iterate 创建无限流,并使用 limit 截断流。
3. 使用 filter 过滤出满足条件的元素。
4. 使用 count 统计满足条件的元素数量。
*/
import java.util.stream.*;
public class SolutionStream {
public long preimageSizeFZF(int k) {
return Stream.iterate(0L, n -> n + 1)
.limit(5L * (k + 1))
.filter(n -> trailingZeroes(n) == k)
.count();
}
private long trailingZeroes(long n) {
long count = 0;
while (n > 0) {
n /= 5;
count += n;
}
return count;
}
}
解释
方法:
题解采用了二分查找的方法来确定具有k个末尾0的最小和最大的x值。首先,函数f(n)计算n的阶乘末尾0的数量,这是通过计算n可以被5的多少次幂整除来实现的。对于给定的k,通过使用两次二分查找,一次寻找满足f(x) = k的最小x值,另一次寻找最大x值。如果k不可能达到(如中间出现跳跃),这两个查找返回的区间会是空的,否则区间内每一个整数都满足条件。搜索范围设定在4k到5(k+1)之间是基于阶乘末尾0的数量增长的大致速度推导出的。
时间复杂度:
O(log^2(n))
空间复杂度:
O(1)
代码细节讲解
🦆
为什么选择将搜索范围设定为从4k到5(k+1),这个范围的确定依据是什么?
▷🦆
在二分查找中,为何第一次和第二次二分查找的条件判断不同?第一次是寻找f(x) >= k的最小x值,而第二次是寻找f(x) <= k的最大x值,请解释调整条件的原因。
▷🦆
在计算阶乘的末尾0的数量时,为什么只需要考虑n能被5的多少次幂整除?2的因子对结果没有影响吗?
▷