Problem Statement in English

You’re given a positive integer k. You need to find the length of the smallest positive integer n such that:

  • n is divisible by k.
  • n consists only of the digit 1.

Approach

So there’s some math behind this problem. I’m going to try and demonstrate it.

Let’s say that k is $3$.

Part 1

Since the number that we’re looking for is made up of purely $1$:

  • $1 \mod 3 = 1$
  • $11 \mod 3 = 2$
  • $111 \mod 3 = 0$

And the answer ends up being $3$. We need $3$ digits of $1$ to get a number divisible by $3$.

Part 2

Parallely, we can also see that:

  • $1 \mod 3 = 1$

Now we take this result, multiply by $10$ and add $1$:

  • $(1 \times 10 + 1) \mod 3 = 2$

Now we take this result, multiply by $10$ and add $1$:

  • $(2 \times 10 + 1) \mod 3 = 0$

We get the same results. But why?

Part 3

And this is because, let’s just go back to the Part 1 calculations, and expand them:

  • $1 \mod 3 = 1$

Now, let’s take that last equation as-is, and multiply both sides by $10$ and add $1$, and then take modulo $3$:

  • $((1 \mod 3) * 10 + 1) \mod 3 = (1 * 10 + 1) \mod 3$

And here is where you can see that we can achieve the same result by operating on the previous result instead of the whole number.

It’s smaller and easier to work with than 1, 11, 111, 1111, ....

Further, we know that when we take modulo $k$, the result is always between $0$ and $k-1$. So there are only $k$ possible remainders.

This means that if we keep calculating the next remainder, we will eventually either:

  • Hit $0$, in which case we have our answer
  • Start repeating remainders, in which case we will never hit $0$ and the answer is $-1$

So the question boils down to cycle detection. If we ever hit a remainder we’ve seen before, we can know that we will never hit $0$, and the answer is $-1$. Otherwise we just keep going.

Below are 2 versions of the solution - one using a set to track seen remainders, and another which is space optimised to $O(1)$ by noting that if we don’t hit $0$ within $k$ iterations, we will never hit it.

Solution in Python

Set Based Approach

Results in $O(n)$ space complexity, and $O(n)$ time complexity


class Solution:
    def smallestRepunitDivByK(self, k: int) -> int:
        seen = set()
        curr = res = 1

        while curr % k:
            if curr in seen:
                return -1

            seen.add(curr)
            curr = 10 * curr % k + 1
            res += 1

        return res

Space Optimised

Results in $O(1)$ space complexity, and $O(n)$ time complexity


class Solution:
    def smallestRepunitDivByK(self, k: int) -> int:
        curr = 1
        for i in range(1, k + 1):
            if curr % k == 0:
                return i

            curr = 10 * curr % k + 1

        return -1

Mistakes I Made

I had to watch the NeetCode video to understand the technique

And we are done.