阶乘相关

发表于 | 分类于 ， | | 阅读次数:

阶乘相关

1. 问题分类

  1. 输入一个非负整数 n，请你计算阶乘 n! 的结果末尾有几个 0
  2. 输入一个非负整数 K，请你计算有多少个 n，满足 n! 的结果末尾恰好有 K 个 0。

1.1 求 n! 的结果末尾有几个 0

n! = 1 * 2 * 3 * … * n

产生1个0，一定是 2 * 5 产生的，所以求0的个数就可以转换成 n! 能拆成多少个因子 2 和 5 => 每一个偶数都可以拆出来最少一个因子 2，所以目标改成求能拆出来多少个因子 5

假设 n = 25，那么 25! 里面包含了多少个因子5结果末尾就有多少个0
25 / 5 = 5 => 这个结果表示，25里有5个是5的倍数的因子，即5、10、15、20、25这样5个，这些因子最少可以提供一个因子5
同时，对于 25 本身来说可以拆成 55，还可以提供*1**个因子5
∴ 25! 的结果末尾有 5 + 1 = 6个0

假设 n = 125，那么 125! 里面包含了多少个因子5结果末尾就有多少个0
125 / 5 = 25 => 这个结果表示，125里有25个是5的倍数的因子，即5、10、15、20、25…125这样25个，这些因子最少可以提供一个因子5
125 / (55) = 5 => 这个结果表示，125 里还有5个是25的倍数的因子，这些因子还可以再提供1个因子5
125本身来说可以拆成 `555`，还可以提供*1**个因子5
∴ 125! 的结果末尾有 25 + 5 + 1 = 31个0

1
2
3
4
5
6
7
8
9
int trailingZeroes(int n) {
    int res = 0;
    long divisor = 5;
    while (divisor <= n) {
        res += n / divisor;
        divisor *= 5;
    }
    return res;
}

这里divisor变量使用 long 型，因为假如n比较大，考虑 while 循环的结束条件，divisor可能出现整型溢出。

1
2
3
4
5
6
7
int trailingZeroes(int n) {
    int res = 0;
    for (int d = n; d / 5 > 0; d = d / 5) {
        res += d / 5;
    }
    return res;
}

1.2 求满足 n! 结果末尾有k个0的个数

首先可以暴力穷举

1
2
3
4
5
6
7
8
9
10
11
12
13
int res = 0;
for (int n = 0; n < +inf; n++) {
    if (trailingZeroes(n) < K) {
        continue;
    }
    if (trailingZeroes(n) > K) {
        break;
    }
    if (trailingZeroes(n) == K) {
        res++;
    }
}
return res;

对于这种具有单调性的函数，用 for 循环遍历，可以用二分查找进行降维打击

搜索有多少个n满足trailingZeroes(n) == K，其实就是在问，满足条件的n最小是多少，最大是多少，最大值和最小值一减，就可以算出来有多少个n满足条件了，也就是二分查找的左边界和右边界

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
long leftBound(int K) {
    long lo = 0, hi = 10;
    while (lo < hi) {
        long mid = lo + (hi - lo) / 2;
        if (trailingZeroes(mid) < K) {
            lo = mid + 1;
        } else if (trailingZeroes(mid) > K) {
            hi = mid - 1;
        } else {
            hi = mid;
        }
    }
    return lo;
}

long rightBound(int K) {
    long lo = 0, hi = 10;
    while (lo < hi) {
        long mid = lo + (hi - lo) / 2;
        if (trailingZeroes(mid) < K) {
            lo = mid + 1;
        } else if (trailingZeroes(mid) > K) {
            hi = mid - 1;
        } else {
            lo = mid + 1;
        }
    }
    return lo;
}

当前针对这道题来说，单纯解题而言，有一个思路是：这个题只能是0或者5。要不然找不到，找到的话就肯定是5个，因为假设找到的数是25，那么26 27 28 29一定也符合。