LeetCode 1015 - Smallest Integer Divisible by K

LeetCode Problem 1015

Difficulty: 🟡 Medium
Topics: Hash Table, Math

Solution

Problem Understanding

The problem asks us to find the length of the smallest positive integer that satisfies two conditions:

1. The integer contains only the digit 1
2. The integer is divisible by k

Such numbers are commonly called repunits. Examples include:

• 1
• 11
• 111
• 1111

The key detail is that we do not need to return the number itself. We only return its length.

For example, if k = 3, the smallest repunit divisible by 3 is 111, so the answer is 3.

The constraint that n may not fit in a 64-bit signed integer is extremely important. It tells us that we cannot actually construct these huge integers directly. Even for moderate values of k, the repunit could become astronomically large.

The input consists of a single integer k, where:

1 <= k <= 10^5

This means the algorithm must be efficient enough to handle values up to one hundred thousand.

There are also important mathematical edge cases. Any number made entirely of 1s always ends with digit 1, so it can never be divisible by 2 or 5. Therefore:

• If k is divisible by 2, no solution exists
• If k is divisible by 5, no solution exists

These cases must immediately return -1.

Another important observation is that there are only k possible remainders when dividing by k. This fact becomes the foundation of the optimal solution.

Approaches

Brute Force Approach

The brute force approach repeatedly constructs repunits:

1
11
111
1111
...

At each step, we check whether the current number is divisible by k.

For example:

current = 1
current = 11
current = 111
current = 1111

This approach is correct because eventually either:

• We find a repunit divisible by k
• Or the numbers grow forever without success

However, this approach quickly becomes impractical because the numbers become enormous. Even storing the integer is impossible for large inputs. Integer overflow would occur long before reaching the answer.

The time complexity is also poor because each new number becomes larger and more expensive to manipulate.

Optimal Approach

The key insight is that we never need the full number itself. We only care about its remainder when divided by k.

Suppose we already know:

remainder = current_number % k

When we append another digit 1, the new number becomes:

new_number = current_number * 10 + 1

Therefore:

new_remainder = (remainder * 10 + 1) % k

This allows us to simulate the growth of the repunit using only remainders, which always stay in the range [0, k-1].

Because there are only k distinct remainders, one of two things must happen:

• We eventually reach remainder 0, meaning divisibility
• Or a remainder repeats, creating a cycle

If a cycle occurs before reaching 0, no solution exists.

Since there are at most k unique remainders, we only need at most k iterations.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²) or worse	O(n)	Constructs gigantic integers directly
Optimal	O(k)	O(1)	Uses modular arithmetic and remainders only

Algorithm Walkthrough

Optimal Algorithm

1. First, check whether k is divisible by 2 or 5.

Any number containing only digit 1 always ends in 1, so it can never be divisible by 2 or 5. If either condition is true, immediately return -1. 2. Initialize a variable called remainder to 0.

This variable represents the remainder of the current repunit when divided by k. 3. Iterate from length 1 up to k.

We only need at most k iterations because there are only k distinct remainders possible. 4. In each iteration, append another digit 1 using modular arithmetic.

Instead of building the actual number, compute:

remainder = (remainder * 10 + 1) % k

This simulates adding a new 1 digit to the end of the current repunit. 5. After updating the remainder, check whether it equals 0.

If the remainder becomes 0, the current repunit is divisible by k, so return the current length. 6. If the loop finishes without reaching remainder 0, return -1.

This means the remainders entered a cycle and no valid repunit exists.

Why it works

The algorithm works because modular arithmetic preserves divisibility properties. At every step, remainder exactly matches the remainder of the current repunit divided by k.

Since there are only k possible remainders, the process must either:

• Reach remainder 0
• Or repeat a previous remainder

Repeating a remainder means the process has entered a cycle and will continue forever without ever reaching 0. Therefore, if no solution appears within k iterations, no solution exists.

Python Solution

class Solution:
    def smallestRepunitDivByK(self, 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 implementation begins with the mathematical impossibility check for divisibility by 2 or 5. This avoids unnecessary computation for cases that can never succeed.

The variable remainder stores the current repunit modulo k. Initially, before any digits are added, the remainder is 0.

The loop runs from 1 through k inclusive because there can be at most k distinct remainders.

Inside the loop, the expression:

remainder = (remainder * 10 + 1) % k

simulates appending digit 1 to the current repunit. This is the core optimization that avoids constructing enormous integers.

Whenever the remainder becomes 0, the current repunit is divisible by k, so the current length is returned immediately.

If the loop finishes without finding remainder 0, the function returns -1.

Go Solution

func smallestRepunitDivByK(k int) int {
    if k%2 == 0 || k%5 == 0 {
        return -1
    }

    remainder := 0

    for length := 1; length <= k; length++ {
        remainder = (remainder*10 + 1) % k

        if remainder == 0 {
            return length
        }
    }

    return -1
}

The Go implementation follows exactly the same logic as the Python version. Since Go integers are fixed-width, avoiding construction of the actual repunit is even more important. Modular arithmetic keeps all intermediate values safely bounded.

Go does not require special handling for overflow here because:

(remainder*10 + 1)

always remains small enough, since remainder < k and k <= 10^5.

Worked Examples

Example 1: k = 1

We want the smallest repunit divisible by 1.

Iteration	Repunit Length	Computation	Remainder
1	1	(0 * 10 + 1) % 1	0

The remainder becomes 0 immediately, so the answer is:

1

Example 2: k = 2

Before starting the loop:

2 % 2 == 0

Any repunit ends with digit 1, so it can never be even.

Therefore the algorithm immediately returns:

-1

Example 3: k = 3

We simulate repunits using remainders.

Iteration	Repunit	Computation	Remainder
1	1	(0 * 10 + 1) % 3	1
2	11	(1 * 10 + 1) % 3	2
3	111	(2 * 10 + 1) % 3	0

At iteration 3, the remainder becomes 0.

Therefore the answer is:

3

Complexity Analysis

Measure	Complexity	Explanation
Time	O(k)	At most k remainder states are explored
Space	O(1)	Only a few integer variables are used

The time complexity is linear in k because the loop runs at most k times. Each iteration performs only constant-time arithmetic operations.

The space complexity is constant because no auxiliary data structures proportional to input size are allocated.

Test Cases

solution = Solution()

assert solution.smallestRepunitDivByK(1) == 1      # smallest possible input
assert solution.smallestRepunitDivByK(2) == -1     # divisible by 2
assert solution.smallestRepunitDivByK(3) == 3      # 111 divisible by 3
assert solution.smallestRepunitDivByK(5) == -1     # divisible by 5
assert solution.smallestRepunitDivByK(7) == 6      # 111111 divisible by 7
assert solution.smallestRepunitDivByK(9) == 9      # sum of digits divisibility
assert solution.smallestRepunitDivByK(11) == 2     # 11 divisible by 11
assert solution.smallestRepunitDivByK(13) == 6     # larger repeating remainder chain
assert solution.smallestRepunitDivByK(17) == 16    # longer valid sequence
assert solution.smallestRepunitDivByK(19) == 18    # another long sequence
assert solution.smallestRepunitDivByK(25) == -1    # divisible by 5
assert solution.smallestRepunitDivByK(100000) == -1  # large impossible input

Test	Why
k = 1	Smallest valid input
k = 2	Impossible because repunits are odd
k = 3	Basic successful example
k = 5	Impossible because repunits end in 1
k = 7	Valid case with moderate length
k = 9	Tests divisibility through digit sums
k = 11	Small non-trivial valid case
k = 13	Tests repeated remainder progression
k = 17	Longer sequence stress test
k = 19	Another longer valid sequence
k = 25	Multiple of 5, immediate failure
k = 100000	Upper bound impossible case

Edge Cases

One important edge case occurs when k is divisible by 2. Any repunit always ends with digit 1, which means it is always odd. A naive implementation might continue searching forever, but the optimized solution immediately detects this condition and returns -1.

Another critical edge case is when k is divisible by 5. Numbers divisible by 5 must end in 0 or 5, but repunits always end in 1. Without the early check, the algorithm would waste time exploring impossible states. The implementation correctly handles this by returning -1 immediately.

A third important edge case involves large values of k, especially near 10^5. Constructing actual repunit integers would overflow standard numeric types or consume excessive memory. The implementation avoids this completely by storing only remainders. Since remainders are always less than k, all computations remain efficient and safe.

Another subtle edge case is the possibility of entering a repeating remainder cycle. Since there are only k possible remainders, repeating one means the sequence will loop forever without reaching divisibility. The implementation handles this implicitly by limiting the loop to at most k iterations.