題目描述
設計一個演算法，計算出n階乘中尾部零的個數
樣例 1： 輸入： 11 輸出： 2 樣例解釋： 11！ = 39916800， 結尾的0有2個。樣例 2： 輸入： 5 輸出： 1 樣例解釋： 5！ = 120， 結尾的0有1個。
題目分析
樸素解法
首先求出n！，然後計算末尾0的個數。（重複÷10，直到餘數非0）
該解法在輸入的數字稍大時就會導致階乘得數溢位，不足取。
O（logn）解法
一個更聰明的解法是：考慮n！的質數因子。字尾0總是由質因子2和質因子5相乘得來的。如果我們可以計數2和5的個數，問題就解決了。考慮下面的例子：
n = 5： 5！的質因子中 （2 * 2 * 2 * 3 * 5）包含一個5和三個2。因而後綴0的個數是1。
n = 11： 11！的質因子中（2^8 * 3^4 * 5^2 * 7）包含兩個5和三個2。於是字尾0的個數就是2。
我們很容易觀察到質因子中2的個數總是大於等於5的個數。因此只要計數5的個數就可以了。那麼怎樣計算n！的質因子中所有5的個數呢？一個簡單的方法是計算floor（n/5）。例如，7！有一個5，10！有兩個5。除此之外，還有一件事情要考慮。諸如25，125之類的數字有不止一個5。例如，如果我們考慮28！，我們得到一個額外的5，並且0的總數變成了6。處理這個問題也很簡單，首先對n÷5，移除所有的單個5，然後÷25，移除額外的5，以此類推。下面是歸納出的計算字尾0的公式。
28！ 因子包含 5， 10， 15， 20， 25 = 5*1， 5 *2， 5 * 3， 5*4， 5*5
n！字尾0的個數 = n！質因子中5的個數
= floor（n/5） + floor（n/25） + floor（n/125） + 。。。。
O（logn） = log（5， n） + log（25， n） + log（125， n） 。。。
注：log（5， n）表示log以5為底的n
原始碼
class Solution： # @param n a integer # @return ans a integer # 解題關鍵是使用以下公式 # n！字尾0的個數 = n！質因子中5的個數 # = floor（n/5） + floor（n/25） + floor（n/125） + 。。。。 def trailingZeros（self， n）： x = 5 ans = 0 while n >= x： ans += n / x x *= 5 return ans
影片教程
影片載入中。。。
