[LeetCode] 1015 | Smallest Integer Divisible by K | Python

---

문제 링크: https://leetcode.com/problems/smallest-integer-divisible-by-k/

---

문제

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.

---

조건

• 1 <= k <= $10^5$

---

내 풀이

2나 5의 배수는 절대 해당 조건을 만족할 수 없으므로 제외한다.

1로만 이루어진 모든 수에 대해서 나눠지는지 확인한다.

이때, 무한정으로 커지지 않게하기 위해서 계속 k로 나눠준다. (n = (n*10 + 1) % k)

---

코드

class Solution:
    def smallestRepunitDivByK(self, k: int) -> int:
        if k%2 == 0 or k%5 == 0: return -1
        
        check = [0] * k
        ans, n = 0, 0
        
        while 1:
            ans += 1
            n = (n*10 + 1) % k
            if n == 0:
                return ans
            if check[n]:
                return -1
            check[n] = 1