算法leetcode

【二分难题】力扣793-阶乘函数后K个零

字数统计: 1.1k字   |   阅读时长: 4分
, ,

摘要: 本文详细拆解 leetcode 793-阶乘函数后K个零

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

今天我们看一类阶乘的问题，力扣 793，有多少个整数的阶乘末尾有 K 个零的问题。通过值域二分可以将该问题转化为给定一个整数，其阶乘末尾有多少零。这正是力扣 172。本文我们就解决这两道题。

题目1

172. 阶乘后的零

给定一个整数 n ，返回 n! 结果中尾随零的数量。

提示：

1
2
n! = n * (n - 1) * (n - 2) * ... * 3 * 2 * 1
0 <= n <= 1e4

示例 1：

输入：n = 3
输出：0
解释：3! = 6 ，不含尾随 0
示例 2：

输入：n = 5
输出：1
解释：5! = 120 ，有一个尾随 0
示例 3：

输入：n = 0
输出：0

算法：数学

$n!$ 末尾 0 的个数即为 $n!$ 中因子 10 的个数。由于 $10 = 2 \times 5$，而质因数 5 的个数不会大于质因数 2 的个数，因此 $n!$ 末尾 0 的个数等于 $n!$ 中质因子 5 的个数。

而 $n!$ 中质因子 $p$ 的个数等于 $[1, n]$ 中每个数的质因子 p 的个数之和，记为 $f(n, p)$。

对于质因子 $p$，考虑 $[1, n]$ 中有多少个 $p$ 的倍数，记为 $n_{1} = \lfloor\frac{n}{p}\rfloor$，这些因子对答案的贡献即为 $n_{1}$。

考虑因子 $p^{2}$，$[1, n]$ 中 $p^{2}$ 的倍数的个数记为 $n_{2} = \lfloor\frac{n}{p^{2}}\rfloor$，这些因子对答案的贡献为 $2n_{2}$，但注意这 $n_{2}$ 个数也是 $p$ 的倍数，这部分贡献在 $n_{1}$ 中已经包含了。因此 $[1, n]$ 中因子 $p^{2}$ 对答案的贡献为 $n_{2}$。

类似地，考虑因子 $p^{k}$，$[1, n]$ 中 $p^{k}$ 的倍数的个数记为 $n_{k} = \lfloor\frac{n}{p^{k}}\rfloor$，将 $p, p^{2}, \cdots p^{k-1}$ 中已经记录的贡献排除后，$p^{k}$ 对答案的贡献为 $n_{k}$。

因此：

本题是 $p = 5$ 的情况，代入公式，结果如下：

代码 (C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int trailingZeroes(int n) {
        // N! 结尾 0 的个数
        int ans = 0;
        if(n < 5) return ans;
        while(n >= 5)
        {
            ans += n / 5;
            n /= 5;
        }
        return ans;
    }
};

题目2

793. 阶乘函数后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，找出多少个非负整数x ，有 f(x) = K 的性质。

注意：

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

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

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

算法: 值域二分

问阶乘后的零个数为 K 的数字有多少个很难，但是如果给定了数字，问阶乘后的零个数就很简单了，如下：

求 $n!$ 结尾 0 的个数，记为 $f(n)$，这正是 172. 阶乘后的零 解决的问题，这里可以直接用结论：

$f(n)$ 是单调的，因此可以二分地找出使得 $f(n) = K$ 的 n 的范围。

另外通过分析可以得到：如果存在某个 x 使得 f(x) = K，那么一定存在连续 5 个数的阶乘末尾零的个数都为 K；如果不存在这样的 x，那么阶乘末尾零的个数为 K 的数字只有 0 个。

代码 (C++)

代码中的 trainling_zero_cnt 函数就是前面的题目的代码，直接用即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
public:
    int preimageSizeFZF(int K) {
        if(K == 0)
            return 5;
        ll left = (ll)1, right = (ll)5 * K + 1;
        while(left < right)
        {
            ll mid = left + (right - left) / 2;
            int cnt = trailing_zero_cnt(mid);
            if(cnt == K)
                return 5;
            else if(cnt < K)
                left = mid + 1;
            else
                right = mid;
        }
        return 0;
    }

private:
    using ll = long long;

    int trailing_zero_cnt(ll n)
    {
        // N! 结尾 0 的个数
        ll ans = 0;
        if(n < 5) return ans;
        while(n >= 5)
        {
            ans += n / 5;
            n /= 5;
        }
        return ans;
    }
};
Share