面试题:计算 n!阶乘的结果的末尾有几个0

前言

首先基于一个事实:我们不可能真的把 n! 的结果计算出来,再去数结果的末尾有几个0;n 很小还好,如果n很大,甚至趋近于无穷大,我们是不可能这样做的。原因主要有二:

  1. 一般计算机的计算能力和存储能力也有限,是计算不出那么大的数的。
  2. 即使计算机能算出来,这样做也很耗时,可能要算很久。

连计算机都算不出来,那我们怎么办呢?别慌,虽然我们不能直接算出结果,但我们可以把问题一步步拆解。

拆解思路

首先,我们想什么情况下会产生一个0?

诶,一个数乘以 10,在末尾就会多出一个 0。而 10 = 5 * 2。

一组数相乘的结果末尾有几个0,取决于这组数因式分解后有几对 5 和 2 的因子。

针对于 n! 这个题目,有这样一个事实:把相乘的数因式分解后,2 的个数肯定大于 5 的个数。

所以,这个问题可以拆解为:只要求出因式分解后有几个 5 的因子即可,5的个数即是末尾出现的0的个数。

解法一:直接法

这种解法的思路是:直接将 n! 中的每个数,按照 5 来因式分解,最后把出现的 5 的个数加起来。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public int calculateZeroInFactorial(int n) {
int count = 0;
// 循环判断所有的乘数
for (int i = n; i > 0; i++) {
if (i % 5 == 0) {
// 如果这个乘数可以对 5 进行因式分解,再看这个乘数可以分解出几个5
int a = i;
while(a % 5 == 0) {
a = a / 5;
count++;
}
}
}
return count;
}

但是这种算法的时间复杂度为 O(nlog(n)),那有没有更快的算法呢?

解法二: log(n) 解法

分析:

  1. n! 这些乘数中,每隔 5 个数,肯定会有一个数至少能拆出一个 5 因子。所以 n / 5 = 至少会出现的 5 的个数。
  2. 上面说至少,因为 n / 5 并不能完全算出 5 因子的个数,比如若某个数 25 = 5 * 5,分解后得到的 5 也算一个,所以能被 25 因式分解相当于会出现 2 个 5 因子,而第一步中除以 5 算个数的时候已经算了一个了,所以相当于比之前会多一个 5 因子。
  3. 依此类推,能被 25 5 = 125 因式分解的相当于比之前按 25 因式分解的时候又多出一个 5 因子。能被 125 5 = 625 因式分解的相当于比按 125 因式分解时又多出一个 5 因子。还有 625 * 5 ……

所以,n! 的结果可以拆分为多少个 5 因子呢?

n/5 + n/25 + n /125 + n/625 + ….

比如 128!的阶乘的结果末尾有几个0呢?

128/5 +128/25 + 128/125 = 25+5+1 = 31 个

又如:1247! 的阶乘的结果末尾有几个0呢?

1247/5 + 1247/25 + 1247/125 + 1247/625 = 249+49+9+1 = 308 个

1
2
3
4
5
6
7
8
public int calculateZeroInLogN(int n) {
int count = 0;
while (n > 0) {
count += n / 5;
n /= 5;
}
return count;
}

这种算法的时间复杂度为 O(log(n)),效率会高很多,而且仅需几行代码。

让我们来一场点赞之交?
0%