題目
難度：★★☆☆☆
類型：數(shù)學(xué)
給定一個(gè)整數(shù) n仅父，返回 n! 結(jié)果尾數(shù)中零的數(shù)量。
示例
示例 1:
輸入: 3
輸出: 0
解釋: 3! = 6, 尾數(shù)中沒有零劣砍。
示例 2:
輸入: 5
輸出: 1
解釋: 5! = 120, 尾數(shù)中有 1 個(gè)零.
說明: 你算法的時(shí)間復(fù)雜度應(yīng)為 O(log n) 链嘀。
解答
我們先來看一下從1到26計(jì)算階乘后的結(jié)果：
1！= 1 0的個(gè)數(shù)為: 0
2潭千！= 2 0的個(gè)數(shù)為: 0
3！= 6 0的個(gè)數(shù)為: 0
4借尿！= 24 0的個(gè)數(shù)為: 0
5刨晴！= 120 0的個(gè)數(shù)為: 1
6！= 720 0的個(gè)數(shù)為: 1
7路翻！= 5040 0的個(gè)數(shù)為: 1
8狈癞！= 40320 0的個(gè)數(shù)為: 1
9！= 362880 0的個(gè)數(shù)為: 1
10茂契！= 3628800 0的個(gè)數(shù)為: 2
11蝶桶！= 39916800 0的個(gè)數(shù)為: 2
12！= 479001600 0的個(gè)數(shù)為: 2
13掉冶！= 6227020800 0的個(gè)數(shù)為: 2
14真竖！= 87178291200 0的個(gè)數(shù)為: 2
15！= 1307674368000 0的個(gè)數(shù)為: 3
16厌小！= 20922789888000 0的個(gè)數(shù)為: 3
17恢共！= 355687428096000 0的個(gè)數(shù)為: 3
18！= 6402373705728000 0的個(gè)數(shù)為: 3
19璧亚！= 121645100408832000 0的個(gè)數(shù)為: 3
20讨韭！= 2432902008176640000 0的個(gè)數(shù)為: 4
21！= 51090942171709440000 0的個(gè)數(shù)為: 4
22！= 1124000727777607680000 0的個(gè)數(shù)為: 4
23透硝！= 25852016738884976640000 0的個(gè)數(shù)為: 4
24狰闪！= 620448401733239439360000 0的個(gè)數(shù)為: 4
25！= 15511210043330985984000000 0的個(gè)數(shù)為: 6
26濒生！= 403291461126605635584000000 0的個(gè)數(shù)為: 6
27埋泵！= 10888869450418352160768000000 0的個(gè)數(shù)為: 6
28！= 304888344611713860501504000000 0的個(gè)數(shù)為: 6
29甜攀！= 8841761993739701954543616000000 0的個(gè)數(shù)為: 6
30秋泄！= 265252859812191058636308480000000 0的個(gè)數(shù)為: 7
很容易觀察到這樣的現(xiàn)象：
從4到5，從9到10规阀，從14到15……階乘中末尾零的個(gè)數(shù)增加恒序，說明5對(duì)于階乘結(jié)果的影響起決定性作用，每乘以一個(gè)含有因子5的數(shù)谁撼，零的個(gè)數(shù)增加一歧胁；
從24到25，階乘中末尾零的個(gè)數(shù)增加2個(gè)厉碟，而這一步相當(dāng)于在24喊巍！的基礎(chǔ)上乘了25，而25恰好是兩個(gè)5相乘箍鼓，實(shí)際上可以與兩個(gè)偶數(shù)配對(duì)崭参，偶數(shù)的個(gè)數(shù)是要遠(yuǎn)遠(yuǎn)多于5的倍數(shù)的。
為此款咖，我們可以得出結(jié)論：將參與乘法運(yùn)算的所有數(shù)進(jìn)行因式分解何暮，所有因子中5的個(gè)數(shù)少于2的個(gè)數(shù)，階乘結(jié)果末尾零的個(gè)數(shù)實(shí)際上等于因子中5的個(gè)數(shù)铐殃。
我們可以通過以下方式求取因子中5的個(gè)數(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)
如有疑問或建議海洼，歡迎評(píng)論區(qū)留言~
