Given an integer n, return the number of trailing zeroes in n!.
最初的代码
class Solution {
public:
int trailingZeroes(int n) {
long long int fac = 1;
int count=0;
if (n==0) fac = 1;
for(int i = n;i>0;i--)
{
fac *= i ;
}
while(fac % 10 == 0)
{
count ++;
fac = fac/10;
}
return count;
}
};报错：
Submission Result: Time Limit Exceeded
看了网上的才知道是质数分解，主要是提取5的个数：
class Solution {
public:
int trailingZeroes(int n) {
int ret = ;
for(int i = ;i<=n;i++)
{
int tem = i;
while(tem % == )
{
ret ++;
tem /= ;
}
}
return ret;
}
};但是 提交后突然 OMG!!!
Last executed input:1808548329
再次在网上寻找原因继续想，进一步简化：
首先1~n中既有5的倍数，还有25的倍数，还是125的倍数等等，而25可以提供两个0，125可以提供3个0，（PS:我自己没有证明过，求大神给出证明，欢迎联系QQ:543451622）
class Solution {
public:
int trailingZeroes(int n) {
int ret = ;
while(n)
{
ret += n/;
n /= ;
}
return ret;
}
};