来源Leetcode第172题阶乘后的零
给定一个整数 n，返回 n! 结果尾数中零的数量。
示例 1:
1
2
3
| 输入: 3
输出: 0
解释: 3! = 6, 尾数中没有零。
|
来源于题解
计算N的阶乘(N!=1*2*...*N)有多少个后缀0，即计算N!里有多少个10，也就是计算N!里有多少个2和5（数学原理：分解质因数），最后结果即2的个数和5的个数取较小值。因此，得到下面时间复杂度为O(NlogN)的暴力求解的算法。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| int trailingZeroes(int n) {
int nCountTwo = 0, nCountFive = 0;
for (int i = 2; i <= n; ++i) {
int value = i;
while (value % 2 == 0) {
++nCountTwo;
value /= 2;
}
while (value % 5 == 0) {
++nCountFive;
value /= 5;
}
}
return std::min(nCountTwo, nCountFive);
}
|
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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
| // 不关注其它质因数，用x代替
0! = 1
1! = 1
2! = 2^1 * 5^0 * 1
3! = 2^1 * 5^0 * 3
4! = 2^3 * 5^0 * 3
5! = 2^3 * 5^1 * 3
6! = 2^4 * 5^1 * 3^2
7! = 2^4 * 5^1 * x
8! = 2^7 * 5^1 * x
9! = 2^7 * 5^1 * x
10! = 2^8 * 5^2 * x
11! = 2^8 * 5^2 * x
12! = 2^10 * 5^2 * x
13! = 2^10 * 5^2 * x
14! = 2^11 * 5^2 * x
15! = 2^11 * 5^3 * x
16! = 2^15 * 5^3 * x
24! = 5^i * x
25! = 5^(i+2) * x
26! = 5^(i+2) * x
27! = 5^(i+2) * x
28! = 5^(i+2) * x
29! = 5^(i+2) * x
30! = 5^(i+3) * x
35! = 5^(i+4) * x
40! = 5^(i+5) * x
45! = 5^(i+6) * x
49! = 5^j * x
50! = 5^(j+2) * x
51! = 5^(j+2) * x
74! = 5^k * x
75! = 5^(k+2) * x
76! = 5^(k+2) * x
-------------------------
125! = 124! * 5^3
250! = 249! * 5^3 * 2
375! = 374! * 5^3 * 3
500! = 499! * 5^3 * 4
625! = 624! * 5^4
|
从上面的数据我们可以看出以下几点
- N!质因数里2的个数总是要比5的个数多，因此此题就变成了求解
N!里有多少个质因数5。这里缺少具体的数学证明，不过解决了这道题，基本就能理解为什么2的个数要比5的个数多了，大致上来说就是每两个数字就会多一个质因数2，而每五个数字才多一个质因数5。
- 每5个数字就会多一个质因数5。0~4的阶乘里没有质因数5，5~9的阶乘里有1个质因数5，10~14的阶乘里有2个质因数5，依此类推。
- 25!里质因数5的个数要比24!多2个，并不满足上面第3条描述的规律。
- 26~49的阶乘仍然满足上面第3条描述的规律；50!里质因数5的个数要比49!多2个，不满足上面第3条描述的规律；51~74的阶乘仍然满足上面第3条描述的规律；依此类推。
- 如果上面第3条规律描述成
每5个一组，N!里质因数5的个数要比前一组多一个，那么上面两点就可以整理成：每25(5^2)个一组，N!里质因数5的个数要比前一组再多一个；依此类推，还可以继续划分成125(5^3)一组，625(5^4)一组，等等。
综上
- N!有多少个后缀0，即N!有多少个质因数5。
- N!有多少个质因数5，即N可以划分成多少组5个数字一组，加上划分成多少组25个数字一组，加上划分多少组成125个数字一组，等等。即
Ans = N/5 + N/(5^2) + N/(5^3) + ...
Ans = N/5 + N/(5^2) + N/(5^3) + ... = ((N / 5) / 5) / 5 /...- 最终算法复杂度为O(logN)，代码如下
1
2
3
4
5
6
7
8
| public int trailingZeroes(int n) {
int cnt = 0;
while(n > 0){
n /= 5;
cnt += n;
}
return cnt;
}
|