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 次浏览

开启你的 职业生涯

完成课程即可获得认证

开始
广告