Smallest Integer Divisible by K: Remainder Cycle Detection

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. In other words, find the shortest "repunit" (1, 11, 111, 1111, ...) that is divisible by k. If no such number exists, return -1.

This is LeetCode 1015: Smallest Integer Divisible by K.

Why this problem matters

At first glance, this looks like it might require working with enormous numbers. The repunit for even a modest k could have hundreds of digits. But the problem is really about modular arithmetic and cycle detection, two patterns that show up constantly in math-related coding problems.

The deeper lesson here is about recognizing when you can reduce a problem to a smaller state space. Instead of building massive numbers, you track only the remainder. This same "track the state, not the full value" idea appears in problems involving hashing, dynamic programming, and graph traversal.

Once you see that the remainder is the only state that matters, the problem collapses from "search through arbitrarily large numbers" to "iterate through at most k remainders." That shift in perspective is the real skill this problem tests.

The key insight

You do not need to compute huge repunit numbers. Notice what happens when you go from one repunit to the next: if the current repunit has value N, the next one is N * 10 + 1. Since you only care about divisibility by k, you can work entirely in the world of remainders: next_remainder = (current_remainder * 10 + 1) % k.

This means you never need to store or manipulate numbers larger than k. You just track the remainder at each step. If the remainder ever hits 0, you have found your answer, and the current length is the result. If a remainder repeats before you hit 0, you are stuck in a cycle and will never reach 0, so you return -1.

There is also a quick shortcut: if k is divisible by 2 or 5, the answer is always -1. A number made entirely of 1s is always odd (so never divisible by 2) and never ends in 0 or 5 (so never divisible by 5). Since there are at most k possible remainders (0 through k - 1), you need to check at most k values before either finding 0 or detecting a repeat.

The solution

def smallest_repunit_div_by_k(k: int) -> int:
    if k % 2 == 0 or k % 5 == 0:
        return -1

    remainder = 0
    for length in range(1, k + 1):
        remainder = (remainder * 10 + 1) % k
        if remainder == 0:
            return length

    return -1

The first check handles the impossible cases. If k is even or divisible by 5, no repunit can ever be divisible by k, so you return -1 immediately.

Then you iterate from length 1 up to k. At each step, you compute the next remainder using (remainder * 10 + 1) % k. This mirrors the process of appending a digit 1 to the repunit, but you never build the actual number. If the remainder reaches 0, the current length is your answer.

The loop runs at most k times. By the pigeonhole principle, there are only k possible remainder values (0 through k - 1). If you have not found 0 after k iterations, a remainder must have repeated, meaning you are in a cycle that will never produce 0. In practice, the early k % 2 == 0 or k % 5 == 0 check already eliminates the -1 cases, so the loop always finds 0 for valid inputs.

Visual walkthrough

Let's trace through the algorithm with k = 3 to see how it finds the answer in just three steps.

The walkthrough shows how each step only needs the previous remainder. The numbers 1, 11, and 21 that appear in the intermediate computation are just prev_remainder * 10 + 1, and you immediately take them mod 3. The actual repunit (111) is never constructed.

Complexity analysis

Time: The loop runs at most k iterations. Each iteration does constant work (one multiplication, one addition, one modulo). So the total time is O(k).

Space: You only store a single integer (remainder) plus the loop counter. No hash set or array is needed because the pigeonhole principle guarantees termination within k steps. So space is O(1).

The building blocks

1. Modular arithmetic for remainder tracking

The core technique is computing (remainder * 10 + 1) % k instead of building the full repunit. This is the same principle behind modular exponentiation and many hashing algorithms: you can take the modulo at each step to keep numbers small without affecting the final divisibility check.

remainder = 0
for length in range(1, k + 1):
    remainder = (remainder * 10 + 1) % k

This pattern appears whenever you need to check divisibility of a number that would be too large to store directly. You will see it in problems involving large powers, repeating patterns, and string-to-number conversions.

2. Pigeonhole-based cycle detection

Instead of explicitly tracking which remainders you have seen (using a hash set), you rely on the pigeonhole principle: with k possible remainders and k iterations, a repeat is inevitable if 0 has not appeared. This lets you bound the loop at k iterations and avoid extra space.

if k % 2 == 0 or k % 5 == 0:
    return -1
# At most k iterations needed; pigeonhole guarantees termination
for length in range(1, k + 1):
    # ...

The explicit "early exit for 2 and 5" step is a common optimization in divisibility problems. Recognizing when certain divisors make a problem impossible saves you from running unnecessary iterations.

Edge cases

• k is even: Return -1 immediately. Repunits are always odd, so they can never be divisible by an even number.
• k is divisible by 5: Return -1. Repunits always end in 1, so they are never divisible by 5.
• k = 1: The answer is 1. The repunit "1" is divisible by 1. The loop catches this on the first iteration since 1 % 1 = 0.
• k = 3: The answer is 3. The repunit "111" equals 3 * 37.
• k = 7: The answer is 6. The repunit "111111" equals 7 * 15873.
• Large k values: The algorithm still runs in O(k) time with O(1) space, so it handles k up to 100,000 efficiently.

From understanding to recall

Reading through this solution, the logic is clear: track remainders, check for 0, and rely on the pigeonhole principle for termination. But reproducing it under pressure is a different skill. Two weeks from now, will you remember to use (remainder * 10 + 1) % k instead of trying to build the actual repunit?

That is where spaced repetition helps. CodeBricks breaks this problem into its building blocks, modular remainder tracking and pigeonhole-based loop bounding, and drills them at increasing intervals. You type the code from understanding, not from memorization. After a few review sessions, the pattern of "reduce the problem to remainders and bound the search by the number of possible states" becomes automatic.

Related posts

• Fraction to Recurring Decimal - Another problem where tracking remainders reveals a cycle, using the same "have I seen this state?" pattern applied to long division
• Happy Number - Cycle detection in a number sequence using a hash set, the same structural idea of checking whether a computed state repeats
• Palindrome Number - Digit manipulation with modular arithmetic, the same mod/div building block used to extract and process digits without string conversion

Mastering these math patterns is about building fluency with a small set of reusable techniques. CodeBricks helps you isolate each technique, drill it independently, and combine them when a problem demands it. Spaced repetition turns understanding into recall, so the next time you see a problem about divisibility or large numbers, you reach for remainder tracking without hesitation.