問題描述
給定一個整數 n，回傳 n! 結果尾數中零的數量，
示例 1:
輸入: 3
輸出: 0
解釋: 3! = 6, 尾數中沒有零，
示例 2:
輸入: 5
輸出: 1
解釋: 5! = 120, 尾數中有 1 個零.
說明: 你演算法的時間復雜度應為 O(log n) ，
解題思路：
方法1：首先，很容易想到，先求得n！，然后再計算尾數中0的個數，但時間復雜度太高
方法2：
可以發現，如果尾數中有x個0，那么在n！的算式中一定存在x個25，所以只要能夠得到 n ！ 的算式中分解出的25的個數即可，
可以知道，n！算式中 2 的個數一定比 5 的個數多，
因此，此題轉化為求解 n！的算式中分解出的 5 的個數
分為以下幾種情況：
對于5,10,15,20…這些數除以5(5的1次冪)，之后的商再無法整除5，每個這樣的數可以產生1個0
對于25,50,75…這些數除以25(5的2次冪)，之后的商再也無法整除5或25，每個這樣的數可以產生2個0，也即比僅整除5的數多產生1個0
對于125,250…這些數除以125(5的3次冪)，之后的商再也無法整除5或25或125，每個這樣的數可以產生3個0，也即比整除5的數多產生2個0
…
因此，我們可以總結出，5的n次冪可以產生n個0.
那么我們如何n的階乘中有多少個數可以整除5呢，直接用n/5即可，同理，整除25的個數用n/25即可，由于整除25的數也能整除5，因為在整除5的時候計算了一次，所以求整除25的時候計算一次即可，同理可以推出后面的情況，
實作代碼
class Solution {
public int trailingZeroes(int n) {
if(n<5){ //當n<5時階乘后的0的個數直接為0
return 0;
}
int x=5; //從5的1次冪時開始，后面每次迭代時乘以5
int count=0; //階乘后的0的個數為0
while(x<=n){
int temp=n/x; //求出能整除x的個數
count+=temp; //累加
x=x*5;
}
return count;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/261082.html
標籤：其他
下一篇：【C++】多型進階