LeetCode 172 Factorial Trailing Zeroes
概述
https://leetcode.com/problems/factorial-trailing-zeroes/
Could you write a solution that works in logarithmic time complexity?
解法
0 只能来自于 2 * 5，所以我们统计一下可以把 n! 分解出多少个 2 与 5 就能算出结果。
显然 2 的个数要多于 5 的个数，所以问题转换为 1~n 里有多少个 5 的倍数。
不是啦，是转换成 1~n 里能分解出多少个 5。
答案是，int(n/5) + int(n/5^2) + ... int(n/5^m)
class Solution {
public:
int trailingZeroes(int n) {
int count = 0;
int c = n;
while (c / 5 != 0) {
count += c / 5;
c /= 5;
}
return count;
}
};
时间复杂度 O(logn)