→ PogChampLUL: 狼媽最強 03/16 19:32
推 RinNoKareshi: 大師 03/16 19:32
推 wwndbk: 大師 03/16 19:35
推 DJYOSHITAKA: 大濕 03/16 19:35
我獨自leetcode
172. Factorial Trailing Zeros
給一個整數n，請回傳n!的trailing zeros的數目
思路 :
這題就純粹的數學題目
你要求一個整數後面有幾個0，就是去把它進行質因數分解
去看有幾個5*2就有幾個0
而這題的整數是n!，質因數分解後2的數目一定會比5多
所以你去求有幾個5就好
問題變成n!質因數分解後有幾個5?
稍微想一下就可以知道
只要是5的倍數就有1個5、25的倍數有2個5，以此類推5^x會有x個5
n/5->有幾個5的倍數、n/25->有幾個25的倍數.....
就這樣一直到n=0，就可以求出答案了
C Code
int trailingZeroes(int n) {
int ans=0;
while(n!=0){
ans+=n/5;
n/=5;
}
return ans;
}
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 42.73.7.29 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1710588707.A.8DA.html