题目来源
Given an integer n, return the number of trailing zeroes in n!.
Note: Your solution should be in logarithmic time complexity.
计算n的阶乘的尾零数目。
我一开始想着是遍历一遍所有5和0的，然后依次相加，如下：
class Solution {
public:
int trailingZeroes(int n) {
int r = 0;
for (int i=5; i<=n; i=i+5) {
int cur = i;
while (cur % 10 == 5 || cur % 10 == 0) {
if (cur % 10 == 5) {
cur = cur / 5;
r++;
}
if (cur % 10 == 0) {
cur = cur / 10;
r++;
}
}
}
return r;
}
};
但是这样做确实有点傻，TLE。得研究一下0尾零的增长规律。发现实现起来还是很简单的，要注意考虑溢出的情况。如下：
class Solution {
public:
int trailingZeroes(int n) {
int r = 0;
long long x = 5;
while (n >= x) {
r += n / x;
x *= 5;
}
return r;
}
};
