Smallest Integer Divisible by K

We want to find the length of the smallest positive integer ( n ) that is divisible by ( k ), and ( n ) contains only the digit 1.

Here’s the Python code:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution:
    def smallestRepunitDivByK(self, k: int) -> int:
        # If k is even or divisible by 5, there's no solution
        if k % 2 == 0 or k % 5 == 0:
            return -1

        # Start with n = 1
        n = 1
        length = 1

        # Keep adding 1 to the number and taking the remainder with k
        while n % k != 0:
            n = (n * 10 + 1) % k
            length += 1

            # If we have looped k times without finding a solution, there is no solution
            if length > k:
                return -1

        return length

Explanation:

1. If ( k ) is even or divisible by 5, there is no solution. This is because any number composed of only the digit 1 will be odd, and its last digit won’t be divisible by 5.
2. Start with ( n = 1 ) and keep appending 1 to it until we find a number that is divisible by ( k ).
3. Since we only care about the remainder, we can work with ( n \mod k ) to prevent overflow.
4. If we’ve looped ( k ) times without finding a solution, there’s no solution.

The time complexity of this code is ( O(k) ), and the space complexity is ( O(1) ).