1、題目要求

Given an integer?n, return the number of trailing zeroes in?n!.

Note:?Your solution should be in logarithmic time complexity.

題目意思是求n的階乘后面末尾0的個數，并且時間復雜度是對數級別。

2、分析

? ? ?一個數 n 的階乘末尾有多少個 0 取決于從 1 到 n 的各個數的因子中 2 和 5 的個數, 而 2 的個數是遠遠多余 5 的個數的, 因此求出 5 的個數即可. 題解中給出的求解因子 5 的個數的方法是用 n 不斷除以 5, 直到結果為 0, 然后把中間得到的結果累加. 例如, 100/5 = 20, 20/5 = 4, 4/5 = 0, 則 1 到 100 中因子 5 的個數為 (20 + 4 + 0) = 24 個, 即 100 的階乘末尾有 24 個 0. 其實不斷除以 5, 是因為每間隔 5 個數有一個數可以被 5 整除, 然后在這些可被 5 整除的數中, 每間隔 5 個數又有一個可以被 25 整除, 故要再除一次, ... 直到結果為 0, 表示沒有能繼續被 5 整除的數了.?

代碼如下：

1 class Solution { 2 public: 3 int trailingZeroes(int n) 4 { 5 int counter=0; //the counter! 6 int k=n; 7 8 while(k>=5) 9 { 10 k=k/5; 11 counter+=k; 12 } 13 14 return counter; 15 } 16 };

?

轉載于:https://www.cnblogs.com/LCCRNblog/p/4392402.html

創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的Leetcode 172 Factorial Trailing Zeroes的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。