開源地址：點擊該鏈接
題目描述
https://leetcode-cn.com/problems/factorial-trailing-zeroes
給定一個整數 n，回傳 n! 結果尾數中零的數量，
示例 1:
輸入: 3
輸出: 0
解釋: 3! = 6, 尾數中沒有零，
示例 2:
輸入: 5
輸出: 1
解釋: 5! = 120, 尾數中有 1 個零.
說明:
你演算法的時間復雜度應為O(logn)，
解題思路
最直接的解法就是先求出 n! 等于多少
然后計算尾數中零的數量，該方法的復雜度為 O(n)
如果想實作復雜度為 O(logn)
必須另想方法，既然我們要計算尾數中的零的個數
等價于我們要計算 n! 中含有多少個 10 這個因子
再進一步的說，10 = 2 * 5，這兩個因子已無法再分解了
原問題再次等價于計算 n! 中含有多少對 (2, 5) 因子
很顯然，在 n! = 1*2*3*4*5*6*...*(n-1)*n 中
2 這個因子出現的次數肯定 >= 5 出現的次數
故原問題又等價于計算 n! 中因子 5 出現的次數
而所有可能出現在含有 5 的數如下：
5^1, 5^2, 5^3, 5^4, 5^5..., 5^max_exp
所以該題的解就是計算如下結果：
(n/5^1 + n/5^2 + n/5^3 + n/5^4 + n/5^5 + ... + n/5^max_exp)
示例代碼
class Solution {
public:
int trailingZeroes(int n) {
int max_exp = log(n) / log(5);
int res = 0;
for (int i=0; i<max_exp; i++) {
int temp = n / 5;
res += temp;
n = temp;
}
return res;
}
};
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/6687.html
標籤：其他