Factorial Trailing Zeroes
描述
Given an integer n
, return the number of trailing zeroes in n!
.
Note: Your solution should be in logarithmic time complexity.
分析
对任意一个正整数n进行质因数分解, ,末尾0的个数M与2和5的个数即X、Z有关,每一对2和5都可以得到10,故M=min(X,Z)
。又因为能被2整除的数出现的频率要比能被5整除的数出现的频率高,所以M=Z
。所以只要计算出Z,就可以得到n!
的末尾0的个数。
解法1
解法2
上面的解法会超时,可以优化一下。
可以用公式计算出末尾0的个数, , 表示从1到N中能被5整除的数的个数,由于每个数都能贡献一个5,意味着能贡献一个0。 表示从1到N中能被 整除的数的个数,每个数都能贡献2个5,意味着能贡献两个0,不过由于其中一次已经包含在 中了,只能再贡献一个0,依次类推。