跳转至

LeetCode: 1015. 可被 K 整除的最小整数

1、题目描述

给定正整数 K,你需要找出可以被 K 整除的、仅包含数字 1 的最小正整数 N

返回 N 的长度。如果不存在这样的 N,就返回 -1

示例 1:

输入:1
输出:1
解释:最小的答案是 N = 1,其长度为 1。

示例 2:

输入:2
输出:-1
解释:不存在可被 2 整除的正整数 N 。

示例 3:

输入:3
输出:3
解释:最小的答案是 N = 111,其长度为 3。

提示:

  • 1 <= K <= 10^5

2、解题思路

  • 首先排除一些因素
    • 被2整除的,结尾肯定是偶数,因此不会存在
    • 被5整除的,结尾肯定是0,5,因此不会存在
  • 不断的增加数字,每次乘以10并加1,判断是否整除,整除则得到结果值
class Solution:
    def smallestRepunitDivByK(self, K: int) -> int:
        if K % 2 == 0 or K % 5 == 0:
            return -1

        num = 1 % K
        ans = 1
        while num:
            num = (num * 10 + 1) % K
            ans += 1
        return ans