【leetcode】1022. Smallest Integer Divisible by K

题目如下：

Given a positive integer K, you need find the smallest positive integer N such that N is divisible by K, and N only contains the digit 1.

Return the length of N. If there is no such N, return -1.

Example 1:
Input: 1

Output: 1

Explanation: The smallest answer is N = 1, which has length 1.
Example 2:
Input: 2

Output: -1

Explanation: There is no such positive integer N divisible by 2.
Example 3:
Input: 3

Output: 3

Explanation: The smallest answer is N = 111, which has length 3.
Note:

1 <= K <= 10^5

解题思路：题目要求找出最小的一个X,使得K*X = 111.....111，一开始我的思路是找出这样的X，例如K=19937，那么X的最后一位一定是3，接下来再计算X的倒数第二位，但是这样会超时，可能是掉入了死循环。其实反过来想想，我们可以111.....111去除以K，判断能否被K整除。首先找出大于或等于K的最小的11...11，然后除以K得到余数，余数后面继续加上最少数量的1使得余数大于K，然后再除以K直到余数为0为止。对于无法被整除的情况，经过若干次操作之后，一定会出现重复的余数，只要用字典记录出现过的余数，如果有重复出现则返回-1。

代码如下：

class Solution(object):

    def smallestRepunitDivByK(self, K):

        """

        :type K: int

        :rtype: int

        """

        len_k = len(str(K))

        res = len_k

        div = '' * (len_k)

        if int(div) < K:

            div += ''

            res += 1

        dic_remainder = {}

        while True:

            remainder = int(div) % K

            if remainder == 0:

                return res

            elif remainder in dic_remainder:

                return -1

            dic_remainder[remainder] = 1

            sr = str(remainder)

            div = sr + '' * (len_k - len(sr))

            res += (len_k - len(sr))

            if int(div) < K:

                div += ''

                res += 1

巴特西

【leetcode】1022. Smallest Integer Divisible by K

最新文章

热门文章