问题
Given an integer n, return the number of trailing zeroes in n!.
Note: Your solution should be in logarithmic time complexity.
例子
10
24
分析
n! = 1*2*3*...*n. 要让n!的末尾有0，1...n中必须有若干数字有2和5的因子，因为2*5=10。由于因子2的数量肯定要远远多于因子5的数量，所有我们只考虑因子5就行了。进一步来说，n!末尾0的数量就等于1...n这n个数中所含有的因子5的数量。
举个例子，27! = 1*2*3...*25*6*27，包含因子5的个数=1(5=1X5) + 1(10=2X5) + 1(15=3X5) + 1(20=4X5) + 2(25=5X5)=6，所以27! 的末尾有6个0.
那么如果求1...n这n个数所含因子5的个数呢？我们首先把n除5，得到的是1...n中只有一个因子5的数的个数；把n除25，得到的是1...n中只有两个个因子5的数的个数；把n除125，得到的是1...n中只有三个个因子5的数的个数......把n除5m，得到的是1...n中只有m个个因子5的数的个数，直到5m>n。然后把所有这些个数加起来，就是1...n这n个数所含因子5的个数。
要点
要能看出来n!末尾0的数量 = 1...n这n个数中所含有的因子5的数量
时间复杂度
O(logn)
空间复杂度
O(1)
代码
迭代版
class Solution {
public:
int trailingZeroes(int n) {
int count = 0;
// 注意i *= 5可能溢出，所以i定义为long long
for (long long i = 5; i <= n; i *= 5)
count += n / i;
return count;
}
};
递归版
class Solution {
public:
int trailingZeroes(int n) {
return n == 0 ? 0 : n / 5 + trailingZeroes(n / 5);
}
};
