题目
难度：★★☆☆☆
类型：数学
给定一个整数 n，返回 n! 结果尾数中零的数量。
示例
示例 1:
输入: 3
输出: 0
解释: 3! = 6, 尾数中没有零。
示例 2:
输入: 5
输出: 1
解释: 5! = 120, 尾数中有 1 个零.
说明: 你算法的时间复杂度应为 O(log n) 。
解答
我们先来看一下从1到26计算阶乘后的结果：
1！= 1 0的个数为: 0
2！= 2 0的个数为: 0
3！= 6 0的个数为: 0
4！= 24 0的个数为: 0
5！= 120 0的个数为: 1
6！= 720 0的个数为: 1
7！= 5040 0的个数为: 1
8！= 40320 0的个数为: 1
9！= 362880 0的个数为: 1
10！= 3628800 0的个数为: 2
11！= 39916800 0的个数为: 2
12！= 479001600 0的个数为: 2
13！= 6227020800 0的个数为: 2
14！= 87178291200 0的个数为: 2
15！= 1307674368000 0的个数为: 3
16！= 20922789888000 0的个数为: 3
17！= 355687428096000 0的个数为: 3
18！= 6402373705728000 0的个数为: 3
19！= 121645100408832000 0的个数为: 3
20！= 2432902008176640000 0的个数为: 4
21！= 51090942171709440000 0的个数为: 4
22！= 1124000727777607680000 0的个数为: 4
23！= 25852016738884976640000 0的个数为: 4
24！= 620448401733239439360000 0的个数为: 4
25！= 15511210043330985984000000 0的个数为: 6
26！= 403291461126605635584000000 0的个数为: 6
27！= 10888869450418352160768000000 0的个数为: 6
28！= 304888344611713860501504000000 0的个数为: 6
29！= 8841761993739701954543616000000 0的个数为: 6
30！= 265252859812191058636308480000000 0的个数为: 7
很容易观察到这样的现象：
-
从4到5，从9到10，从14到15……阶乘中末尾零的个数增加，说明5对于阶乘结果的影响起决定性作用，每乘以一个含有因子5的数，零的个数增加一；
-
从24到25，阶乘中末尾零的个数增加2个，而这一步相当于在24！的基础上乘了25，而25恰好是两个5相乘，实际上可以与两个偶数配对，偶数的个数是要远远多于5的倍数的。
为此，我们可以得出结论：将参与乘法运算的所有数进行因式分解，所有因子中5的个数少于2的个数，阶乘结果末尾零的个数实际上等于因子中5的个数。
我们可以通过以下方式求取因子中5的个数：
class Solution:
def trailingZeroes(self, n):
count = 0
while n > 0:
count += n // 5
n /= 5
return count
写成递归形式是这样：
class Solution:
def trailingZeroes(self, n):
if n < 5:
return 0
return n // 5 + self.trailingZeroes(n // 5)
如有疑问或建议，欢迎评论区留言~
网友评论