Generated by Codex with GPT-5

Quick facts

What the problem is really asking

The input is a positive integer k. The task is to find the length of the smallest positive integer made only of the digit 1 that is divisible by k.

For example:

  • If k = 1, the number 1 works, so the answer is 1.
  • If k = 3, the number 111 works, so the answer is 3.
  • If k = 2, no number ending in 1 can be even, so the answer is -1.

The important detail is that the actual number may be enormous. A repunit with 100,000 digits cannot be built as a normal integer in an interview solution. The problem is really asking for divisibility, so the solution should work with remainders instead of the full number.

The key observation

Every candidate number has this shape:

1
11
111
1111
...

If the current candidate has remainder r when divided by k, appending one more digit 1 creates the next candidate:

next_number = current_number * 10 + 1

The matching remainder update is:

next_remainder = (r * 10 + 1) % k

That single formula lets the algorithm test every candidate length without ever materializing the candidate number.

There is also a quick impossibility check. Any number made only of 1s ends in 1, so it can never be divisible by 2 or 5. If k has either factor, the answer is immediately -1.

Why checking at most k lengths is enough

There are only k possible remainders modulo k: 0 through k - 1.

As the algorithm generates remainders for lengths 1, 2, 3, and so on, one of two things must happen within the first k generated remainders:

  1. A remainder becomes 0, which means the current repunit is divisible by k.
  2. A remainder repeats, which means the sequence has entered a cycle and will keep repeating the same states forever.

Because the next remainder depends only on the current remainder, a repeated remainder cannot later produce a new outcome. So if no length from 1 through k works, no larger length will work either.

Under the original constraints, the factor check for 2 and 5 rules out the common impossible cases. The bounded remainder loop is still useful because it is simple, safe, and proves the algorithm always terminates.

How to derive this in an interview

Start from the warning that the answer number may not fit in a 64-bit integer. That is the prompt’s hint that building 1, 11, 111, and so on directly is the wrong level of representation.

For divisibility by k, only the remainder matters. If two huge numbers have the same remainder modulo k, they behave the same for future append operations. So instead of carrying the number, carry number % k.

Then derive the recurrence out loud:

new_number = old_number * 10 + 1
new_remainder = (old_remainder * 10 + 1) % k

Finally, explain the stopping rule. Since there are only k remainders, either the search finds remainder 0 within k steps or it has cycled. That gives a linear-time solution with constant extra space.

Python solution

class RepunitDivisibilitySolver:
    """Find the shortest all-ones positive integer divisible by k."""

    def __init__(self, divisor: int) -> None:
        if divisor <= 0:
            raise ValueError("divisor must be positive")
        self.divisor = divisor

    def smallest_length(self) -> int:
        if self._has_impossible_last_digit():
            return -1

        remainder = 0

        for length in range(1, self.divisor + 1):
            # Appending digit 1 to the current repunit:
            # new_value = old_value * 10 + 1.
            remainder = (remainder * 10 + 1) % self.divisor

            if remainder == 0:
                return length

        return -1

    def _has_impossible_last_digit(self) -> bool:
        return self.divisor % 2 == 0 or self.divisor % 5 == 0


class Solution:
    def smallestRepunitDivByK(self, k: int) -> int:
        solver = RepunitDivisibilitySolver(k)
        return solver.smallest_length()

The loop runs at most k times, so the time complexity is O(k). The algorithm keeps only the current remainder and a few scalar values, so the extra space complexity is O(1).

Interview follow-ups

Why is it safe not to store a set of seen remainders?

A seen-remainder set is a valid way to explain cycle detection. Each generated repunit length has a remainder modulo k; if a remainder appears twice, the future sequence must repeat from that point because the transition formula depends only on the current remainder.

For this exact problem, a set is not necessary. There are only k possible remainders, so running the loop for at most k iterations gives the same termination guarantee. If remainder 0 has not appeared by then, the search has either already cycled or is forced to cycle next.

The set-based version is slightly more explicit and costs O(k) space. The bounded-loop version is cleaner and keeps the optimal O(1) space bound.

What if the number can use only a repeated digit other than 1?

Suppose the number must be made of a repeated digit d, such as 777...7. The same remainder recurrence works, with d replacing 1:

next_remainder = (current_remainder * 10 + d) % k

The impossibility rule changes. The last digit is now d, so divisibility by 2 or 5 depends on that digit and on k. The most general approach is to skip the special-case rule and use cycle detection with either a seen set or a bounded loop over remainders. If remainder 0 appears, return the length; if the remainder sequence repeats, return -1.

This keeps the runtime O(k) and uses O(1) space with a bounded loop, or O(k) space with explicit cycle tracking.

What if the interviewer asks for the actual all-ones number?

For small answers, the number can be reconstructed as "1" * length after the length is found. That returns the exact decimal representation without risking integer overflow.

The tradeoff is output size. If the answer length is large, returning the string requires O(length) time and O(length) space just to produce the output. That is unavoidable because the caller asked for all digits. The divisibility search still uses O(1) working space before the final string is built.

How would this change if k is very large and there are many queries?

For one query, the linear remainder simulation is already the right practical answer. With many repeated queries, caching answers by k is the simplest improvement if the same divisors appear again.

If the queries are for many different k values, there is no single small precomputation that answers all of them cheaply, because each divisor has its own remainder transition graph. The best shared optimization is to reject divisors with factors 2 or 5 immediately, then run the O(k) simulation for the remaining cases. If query limits are extreme, the interviewer is likely looking for number-theory discussion around the multiplicative order of 10 modulo factors of k, but that is more complex than the usual LeetCode solution and has heavier implementation risk.

Can the answer ever be larger than k?

No. If a solution exists, there is one with length at most k.

The reason is the same pigeonhole argument used for termination. Among the first k repunit remainders, either one is 0, or two nonzero remainders are the same. A repeated nonzero remainder means the process is cycling without having reached divisibility. Therefore a first successful length, when it exists, must appear within those first k attempts.

This is why the loop bound is not just a performance optimization. It is part of the correctness proof.

Practical takeaway

This problem is a compact test of modular arithmetic. The prompt describes a huge decimal number, but divisibility only needs the current remainder. Once the candidate number is replaced by its remainder, appending another 1 becomes a constant-time update, and the finite number of possible remainders gives a clear stopping rule.