Python程式：查詢末尾有n個0的數字m

假設我們有一個數字n。我們需要找到最小的數字m，使得m的階乘至少有n個0。

因此，如果輸入為n = 2，則輸出將為10，因為10！= 3628800，而9！= 362880，具有2個零的最小數字是10。

為了解決這個問題，我們將遵循以下步驟：

• 定義一個函式count_fives()。它將接收n作為輸入。
• cnt := 0
• 當n > 0時，執行以下操作：
  • n := floor(n / 5)
  • cnt := cnt + n
• 返回cnt
• 在主方法中，執行以下操作：
• left := 1
• right := 5^24
• 當right - left > 5時，執行以下操作：
  • mid := floor((right + left) / 10) * 5
  • fives := count_fives(mid)
  • 如果fives等於n，則：
    • right := mid
    • left := right - 5
    • 退出迴圈
  • 否則，如果fives < n，則：
    • left := mid
  • 否則：
    • right := mid
• 返回right

示例

讓我們看看以下實現以更好地理解：

def count_fives(n):
   cnt = 0
   while n > 0:
      n = n // 5
      cnt += n
   return cnt

def solve(n):
   left = 1
   right = 5**24
   while right - left > 5:
      mid = int((right + left) / 10) * 5
      fives = count_fives(mid)
      if fives == n:
         right = mid
         left = right - 5
         break
      elif fives < n:
         left = mid
      else:
         right = mid
   return right

n = 2
print(solve(n))

輸入

2

輸出

10

Arnab Chakraborty

更新於: 2021年10月25日

94 次瀏覽

開啟您的 職業生涯

透過完成課程獲得認證

開始學習