題目
難度：★★☆☆☆
類型：數(shù)學
給定一個整數(shù) n，返回 n! 結(jié)果尾數(shù)中零的數(shù)量。
示例
示例 1:
輸入: 3
輸出: 0
解釋: 3! = 6, 尾數(shù)中沒有零。
示例 2:
輸入: 5
輸出: 1
解釋: 5! = 120, 尾數(shù)中有 1 個零.
說明: 你算法的時間復雜度應(yīng)為 O(log n) 。
解答
我們先來看一下從1到26計算階乘后的結(jié)果：
1！= 1 0的個數(shù)為: 0
2！= 2 0的個數(shù)為: 0
3！= 6 0的個數(shù)為: 0
4！= 24 0的個數(shù)為: 0
5！= 120 0的個數(shù)為: 1
6！= 720 0的個數(shù)為: 1
7！= 5040 0的個數(shù)為: 1
8！= 40320 0的個數(shù)為: 1
9！= 362880 0的個數(shù)為: 1
10！= 3628800 0的個數(shù)為: 2
11！= 39916800 0的個數(shù)為: 2
12！= 479001600 0的個數(shù)為: 2
13！= 6227020800 0的個數(shù)為: 2
14！= 87178291200 0的個數(shù)為: 2
15！= 1307674368000 0的個數(shù)為: 3
16！= 20922789888000 0的個數(shù)為: 3
17！= 355687428096000 0的個數(shù)為: 3
18！= 6402373705728000 0的個數(shù)為: 3
19！= 121645100408832000 0的個數(shù)為: 3
20！= 2432902008176640000 0的個數(shù)為: 4
21！= 51090942171709440000 0的個數(shù)為: 4
22！= 1124000727777607680000 0的個數(shù)為: 4
23！= 25852016738884976640000 0的個數(shù)為: 4
24！= 620448401733239439360000 0的個數(shù)為: 4
25！= 15511210043330985984000000 0的個數(shù)為: 6
26！= 403291461126605635584000000 0的個數(shù)為: 6
27！= 10888869450418352160768000000 0的個數(shù)為: 6
28！= 304888344611713860501504000000 0的個數(shù)為: 6
29！= 8841761993739701954543616000000 0的個數(shù)為: 6
30！= 265252859812191058636308480000000 0的個數(shù)為: 7
很容易觀察到這樣的現(xiàn)象：
從4到5，從9到10，從14到15……階乘中末尾零的個數(shù)增加，說明5對于階乘結(jié)果的影響起決定性作用，每乘以一個含有因子5的數(shù)，零的個數(shù)增加一；
從24到25，階乘中末尾零的個數(shù)增加2個，而這一步相當于在24！的基礎(chǔ)上乘了25，而25恰好是兩個5相乘，實際上可以與兩個偶數(shù)配對，偶數(shù)的個數(shù)是要遠遠多于5的倍數(shù)的。
為此，我們可以得出結(jié)論：將參與乘法運算的所有數(shù)進行因式分解，所有因子中5的個數(shù)少于2的個數(shù)，階乘結(jié)果末尾零的個數(shù)實際上等于因子中5的個數(shù)。
我們可以通過以下方式求取因子中5的個數(shù)：
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)
如有疑問或建議，歡迎評論區(qū)留言~
