【LeetCode 簡單題】40-階乘後的0

聲明：

今天是第40道題。給定一個整數 n，傳回 n! 結果尾數中零的數量。以下所有代碼經過樓主驗證都能在LeetCode上執行成功，代碼也是借鑒别人的，在文末會附上參考的部落格連結，如果侵犯了部落客的相關權益，請聯系我删除

（手動比心ღ( ´･ᴗ･` )）

正文

題目：給定一個整數 n，傳回 n! 結果尾數中零的數量。

示例 1:

輸入: 3
輸出: 0
解釋: 3! = 6, 尾數中沒有零。      

示例 2:

輸入: 5
輸出: 1
解釋: 5! = 120, 尾數中有 1 個零.
      

說明: 你算法的時間複雜度應為 O(log n)  

解法1。注意題幹對時間複雜度的要求，疊代遞歸肯定不滿足，是以這道題需要巧解。這裡先給出其計算公式，推導過程祥見連結。其實有0就意味着有10，是以關系式可以寫成：有0-->有10-->有5*2-->有5（有5必有2，因為2比5小），小于5的階乘都沒有10-->…後面的沒看懂了囧

• 令f(x)表示正整數x末尾所含有的“0”的個數，則有：
  • 當0 < n < 5時，f(n!) = 0;
  •  當n >= 5時，f(n!) = k + f(k!), 其中 k = n / 5（取整）
• 計算舉例
  • f(5!) = 1 + f(1!) = 1
  • f(10!) = 2 + f(2!) = 2
  • f(20!) = 4 + f(4!) = 4
  • f(100!) = 20 + f(20!) = 20 + 4 + f(4!) = 24
  • f(1000!) = 200 + f(200!) = 200 + 40 + f(40!) = 240 + 8 + f(8!) = 248 + 1 + f(1) =249

class Solution(object):
    def trailingZeroes(self, n):
        """
        :type n: int
        :rtype: int
        """
        result = 0
        while n>=5:
            n = int(n/5)
            result += n
   
        return result           

結尾

解法1：https://www.cnblogs.com/hutonm/p/5624996.html（非常值得看）