leetcode
leetcode 701 ~ 750
阶乘函数后 K 个零

阶乘函数后 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),这个范围的确定依据是什么?
选择这个范围是基于阶乘末尾0的数量增长规律。因为每个末尾的0是由因子5和因子2组成的,而在任何给定的数字序列中,因子2的数量总是多于因子5的数量。因此,末尾0的数量主要由因子5的数量决定。一个粗略的估算表明,n的阶乘大约每隔5个数就增加一个额外的末尾0。因此,大约每增加5个新的末尾0,n需要增加大约5的倍数。所以从4k到5(k+1)的范围是一个保守的估计,确保能够涵盖从k个0增加到k+1个0的所有可能的n值。
🦆
在二分查找中,为何第一次和第二次二分查找的条件判断不同?第一次是寻找f(x) >= k的最小x值,而第二次是寻找f(x) <= k的最大x值,请解释调整条件的原因。
第一次二分查找的目的是找到满足f(x) >= k的最小的x值,这意味着找到第一个阶乘尾部有至少k个零的数。这是为了确定满足条件的下界。而第二次二分查找的目的是找到满足f(x) <= k的最大的x值,即找到阶乘尾部零的数量恰好是k的最大数,这是为了确定满足条件的上界。这样通过两次查找,我们可以确定所有满足阶乘尾部有k个零的数的范围。
🦆
在计算阶乘的末尾0的数量时,为什么只需要考虑n能被5的多少次幂整除?2的因子对结果没有影响吗?
在计算阶乘尾部的0的数量时,每个0都来源于因子10,而10可以分解为2和5。在任何给定的n中,产生2的因子的数字(如2、4、6等)比产生5的因子的数字(如5、10、15等)要多,因此2的因子在阶乘中总是充足的。这意味着末尾0的数量完全由因子5的数量决定,因此在计算时只需要关注n能被5的多少次幂整除。

相关问题

阶乘后的零

给定一个整数 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

 

进阶:你可以设计并实现对数时间复杂度的算法来解决此问题吗?