11
04/2015
[LeetCode] Factorial Trailing Zeroes
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!=2^x*3^y*5^z...，注意到一个2和一个5贡献一个末尾的0，因此只需计算min(x,z)即可。又因为n/2和n/5分别表示n!中的因子能被2和5整除的个数，n/2>=n/5，因此min(x, z)=z。我们只需要计算z即可。
如何计算z呢？n/5表示n!中被5整数的个数（贡献至少一个0）， n/(5^2)表示被25整除的个数（贡献至少2个0）...，因此z的计算代码如下：
class Solution {
public:
int trailingZeroes(int n) {
int ret = 0;
while(n)
{
ret += n /= 5;
}
return ret;
}
};扩展思维：
曾经做过，30!的三进制表示中，末尾0的个数有多少个？注意到在三进制中，每逢三便给结果贡献一个0，因此0的个数为30/3+30/9+30/27=14。注意这里的除法是整数除法。
二次刷题（2015-08-06）
class Solution {
public:
int trailingZeroes(int n) {
int result = 0;
while(n!=0){
n = n/5;
result += n;
}
return result;
}
};
0 条评论