給定整數 n,返回 n! 末尾 0 的個數。要求對數時間複雜度。
尾部 0 由因子 10 產生,即 2 和 5 配對。階乘中因子 2 遠多於 5,所以 0 的個數等於因子 5 的個數。每 5 個數貢獻一個 5,每 25 個額外貢獻一個,以此類推。公式:n/5 + n/25 + n/125 + ...
class Solution {
public:
int trailingZeroes(int n) {
int count = 0;
while (n) {
n /= 5;
count += n;
}
return count;
}
};