Leetcode 1015. Smallest Integer Divisible by K: 最小只有1被k整除的長度

 1015. Smallest Integer Divisible by K 

python 解法

Given a positive integer k, you need to find the length of 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.

Note: n may not fit in a 64-bit signed integer.

解法: 數論:

按照定義寫下餘式的recursion

參見python代碼如下

注意 k至多只有k種不同的remainder 所以超過k次以後 就不用再測試了。

class Solution:

    def smallestRepunitDivByK(self, k: int) -> int:

        

        

        if k%2==0:

            return -1

        

        re=0

        for n in range(1,k+1):

            re=(re*10+1)%k

            if re==0:

                return n

        return -1