smallest-integer-divisible-by-k¶

Description¶

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.

Example 1:

Input: k = 1
Output: 1
Explanation: The smallest answer is n = 1, which has length 1.

Example 2:

Input: k = 2
Output: -1
Explanation: There is no such positive integer n divisible by 2.

Example 3:

Input: k = 3
Output: 3
Explanation: The smallest answer is n = 111, which has length 3.

Constraints:

1 <= k <= 10⁵

Solution(Python)¶

class Solution:
    def smallestRepunitDivByK(self, k: int) -> int:
        rem = 1
        len_n = 1

        seen = set()
        while rem % k != 0:
            n = rem * 10 + 1
            rem = n % k
            len_n += 1

            if rem in seen:
                return -1
            else:
                seen.add(rem)
        return len_n