LeetCode 1015: Smallest Integer Divisible by K

Problem Restatement

We need to find the smallest positive integer N consisting only of the digit 1 (a repunit) such that N is divisible by k.

In other words, find the smallest n such that:

N = 111...1  (n ones)
N % k == 0

Return n, or -1 if no such positive integer exists.

The official constraints state that 1 <= k <= 10^5.

Input and Output

Function shape:

def smallestRepunitDivByK(k: int) -> int:
    ...

Examples

Example 1:

k = 1

N = 1, which is divisible by 1.

Answer:

1

Example 2:

k = 2

No repunit is divisible by 2. All repunits are odd numbers.

Answer:

-1

Example 3:

k = 3

N = 111 = 3 * 37, divisible by 3.

Answer:

3

Key Insight

If k is divisible by 2 or 5, no repunit can be divisible by k, because repunits always end in 1 (not an even number or multiple of 5).

Otherwise, we compute the remainder of N_n = 111...1 (n ones) modulo k.

The recurrence is:

N_n = N_{n-1} * 10 + 1
remainder_n = (remainder_{n-1} * 10 + 1) % k

By the pigeonhole principle, if we never hit remainder 0, we will eventually see a repeated remainder after at most k steps. A repeated remainder means we are in a cycle and will never reach 0.

Algorithm

1. If k % 2 == 0 or k % 5 == 0, return -1.
2. Start with remainder = 0.
3. For n from 1 to k:
   • remainder = (remainder * 10 + 1) % k.
   • If remainder == 0, return n.
4. Return -1.

Correctness

By pigeonhole, there are only k possible remainders modulo k. If after k steps we have not found remainder 0, then some remainder has appeared twice. This means the sequence of remainders is periodic and will never reach 0.

Edge Cases

• Duplicates usually matter; store counts when a set would lose necessary multiplicity.
• Update the frequency structure in the same order the invariant assumes.
• Check empty or one-element inputs if the problem allows them.

Complexity

Common Pitfalls

• Do not optimize away the invariant; the code should still make it clear what condition is being maintained.
• Prefer problem-specific names over one-letter variables once the logic becomes stateful.

Implementation

class Solution:
    def smallestRepunitDivByK(self, k: int) -> int:
        if k % 2 == 0 or k % 5 == 0:
            return -1

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

        return -1

Code Explanation

Early exit for even or multiple-of-5 values:

if k % 2 == 0 or k % 5 == 0:
    return -1

Compute remainders iteratively:

remainder = (remainder * 10 + 1) % k

This avoids dealing with very large numbers.

Return the length when the remainder first reaches 0:

if remainder == 0:
    return n

Testing

def run_tests():
    s = Solution()

    assert s.smallestRepunitDivByK(1) == 1
    assert s.smallestRepunitDivByK(2) == -1
    assert s.smallestRepunitDivByK(3) == 3
    assert s.smallestRepunitDivByK(7) == 6
    assert s.smallestRepunitDivByK(5) == -1

    print("all tests passed")

run_tests()