https://leetcode.com/problems/smallest-integer-divisible-by-k

First of all, let us notice, that if number is divisible by 2 or by 5, then we need to return -1 immediatly, because number ending with 1 can not divide by 2 or 5. From now on we assume, that K is not divisible by 2 or 5. Let us consider numbers:

1 11 111 … 111...111,

where were have K ones in the last group. Then, there can be only two cases:

  1. All reminders of given numbers when we divide by K are different.
  2. Some two reminders are equal.

In the first case, we have K numbers and also K possible reminders and they are all different, it means, that one of them will be equal to 0.

In the second case, two numbers have the same reminder, let us say number 11...1111 with a ones and 111...11111 with b ones, where b > a. Then, difference of these two numbers will be divisible by K. What is the difference? It is number 11...1100...000 with b-a ones and a zeroes at the end. We already mentioned that K is not divisible by 2 or 5 and it follows, that 11...111 divisible by K now, where we have b-a ones.

So, we proved the following statements: if K not divisible by 2 and 5, then N <= K. What we need to do now is just iterate through numbers and stop when we find number divisible by K. To simplify our cumputation, we notice, that each next number is previous multiplied by 10 plus 1.

Complexity: time complexity is O(n), space is O(1).

class Solution(object):
    def smallestRepunitDivByK(self, K):
        if K % 2 == 0 or K % 5 == 0: return -1
        rem, steps = 1, 1
        while rem % K != 0:
            rem = (rem*10 + 1) % K
            steps += 1
        return steps

If you like the solution, you can upvote it on leetcode discussion section: Problem 1015