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

  |  

摘要: 本文详细拆解 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