Python 中可被 K 整除的最小整數

假設我們有一個正整數 K，我們需要找到最小的正整數 N，使得 N 可以被 K 整除，且 N 僅包含數字 1。我們需要找到 N 的長度。如果不存在這樣的 N，則返回 -1。因此，如果輸入為 3，則輸出為 3。最小的答案為 N = 111。

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

  • 如果 k 為偶數或者 k 可以被 5 整除，則返回 -1
  • 設定 r := 0 和 N = 1
  • 對於範圍 1 到 K + 1 內的 i
    • r := (r * 10 + 1) mod k
    • 如果 r = 0，則返回 i

我們看看以下執行情況，以獲得更好的理解：

示例

 即時演示

class Solution(object):
   def smallestRepunitDivByK(self, K):
      if K%2==0 or K%5 ==0:
         return -1
      r = 0
      N=1
      for i in range(1,K+1):
         r = (r*10 + 1)%K
         if r == 0:
            return i
ob = Solution()
print(ob.smallestRepunitDivByK(11))

輸入

11

輸出

2

更新於：2020 年 4 月 30 日

242 次瀏覽

開啟你的 職業生涯

完成課程即可獲得認證

開始
廣告