Smallest Integer Divisible by K

Med

#0969Time: O(k^2). The loop runs up to `k` times. In each iteration `i`, the number `n` has `i` digits. `BigInteger` operations like multiplication and modulo on a number with `i` digits take roughly `O(i)` time. The total time is the sum of `O(i)` for `i` from 1 to `k`, which results in `O(k^2)`.Space: O(k). We need to store the `BigInteger` `n`, which can have up to `k` digits. The space required is proportional to the number of digits.

Patterns

Math

Data structures

Hash Table

Prompt

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.

Return the length of n. If there is no such n, return -1.

Note: n may not fit in a 64-bit signed integer.

Example 1:

Input: k = 1
Output: 1
Explanation: The smallest answer is n = 1, which has length 1.

Example 2:

Input: k = 2
Output: -1
Explanation: There is no such positive integer n divisible by 2.

Example 3:

Input: k = 3
Output: 3
Explanation: The smallest answer is n = 111, which has length 3.

Constraints:

1 <= k <= 10⁵

Approaches

2 approaches with complexity analysis and trade-offs.

This approach simulates the process directly. We generate the numbers consisting of only ones (1, 11, 111, ...) and for each number, we check if it's divisible by k. Since these numbers can grow very large and exceed the capacity of standard integer types like long, we must use a data structure that supports arbitrary-precision arithmetic, such as Java's BigInteger.

Algorithm

Initialize a BigInteger variable n to 1.
Initialize a length variable to 1.
Create a BigInteger representation of k.
Start a loop that continues for at most k iterations. This limit is based on the Pigeonhole Principle, which guarantees that if a solution exists, it will be found within k steps.
Inside the loop, check if n is divisible by k using the mod operation: n.mod(k_big_int).equals(BigInteger.ZERO).
If it is divisible, return the current length.
If not, update n to the next number in the sequence: n = n.multiply(BigInteger.TEN).add(BigInteger.ONE).
Increment length.
If the loop finishes, return -1.

Walkthrough

The algorithm iteratively builds the numbers n = 1, 11, 111, ... and checks for divisibility by k.

1import java.math.BigInteger;2 3class Solution {4    public int smallestRepunitDivByK(int k) {5        if (k % 2 == 0 || k % 5 == 0) {6            return -1;7        }8        BigInteger n = BigInteger.ONE;9        BigInteger kBigInt = BigInteger.valueOf(k);10        int length = 1;11        // We only need to check up to k times due to the Pigeonhole Principle.12        while (length <= k) {13            if (n.mod(kBigInt).equals(BigInteger.ZERO)) {14                return length;15            }16            n = n.multiply(BigInteger.TEN).add(BigInteger.ONE);17            length++;18        }19        return -1; // Should not be reached if k is not divisible by 2 or 520    }21}

Complexity

Time

O(k^2). The loop runs up to `k` times. In each iteration `i`, the number `n` has `i` digits. `BigInteger` operations like multiplication and modulo on a number with `i` digits take roughly `O(i)` time. The total time is the sum of `O(i)` for `i` from 1 to `k`, which results in `O(k^2)`.

Space

O(k). We need to store the `BigInteger` `n`, which can have up to `k` digits. The space required is proportional to the number of digits.

Trade-offs

Pros

Conceptually straightforward, directly translating the problem statement.

Cons

Inefficient due to the overhead of BigInteger operations.
Can lead to Time Limit Exceeded on platforms with strict time limits.
Requires external logic (capping iterations at k) to handle the no-solution case correctly.

A much more efficient approach avoids dealing with large numbers altogether by using modular arithmetic. The key idea is that to check if a number n is divisible by k, we only need to know the remainder of n when divided by k (n % k). We can find a recurrence relation for the remainders and compute them iteratively.

Algorithm

First, handle the impossible cases. A number consisting of only '1's can never be divisible by a number ending in 0, 2, 4, 5, 6, or 8. This means if k is divisible by 2 or 5, no solution exists. So, if k % 2 == 0 or k % 5 == 0, return -1.
Initialize a remainder variable rem to 0.
Iterate for length from 1 to k.
In each iteration, update the remainder using the formula: rem = (rem * 10 + 1) % k.
If rem becomes 0, it means the number formed by the current length of ones is divisible by k. We have found the smallest length, so we return length.
If the loop completes without finding a solution, it implies no solution exists (though this case is already covered by the initial check).

Walkthrough

Let n_i be the number formed by i ones. We have the relationship n_i = n_{i-1} * 10 + 1. If we take the modulo k on both sides, we get n_i % k = ( (n_{i-1} % k) * 10 + 1 ) % k. This means we can calculate the remainder for a number of length i using only the remainder of the number with length i-1. We never need to store the large number n_i itself.

The remainders can only take k possible values (0 to k-1). If we don't find a remainder of 0 within k iterations, the Pigeonhole Principle guarantees that at least one non-zero remainder must have been repeated. Once a remainder repeats, we are in a cycle and will never reach 0. Our initial check for divisibility by 2 and 5 ensures that a solution always exists if we pass that check, so the loop is guaranteed to find a solution within k iterations.

1class Solution {2    public int smallestRepunitDivByK(int k) {3        // If k is divisible by 2 or 5, no number made of 1s can be a multiple.4        if (k % 2 == 0 || k % 5 == 0) {5            return -1;6        }7        8        int remainder = 0;9        for (int length = 1; length <= k; length++) {10            // Calculate the remainder of the next number (e.g., 1, 11, 111, ...)11            // n_i = n_{i-1} * 10 + 112            // rem_i = (rem_{i-1} * 10 + 1) % k13            remainder = (remainder * 10 + 1) % k;14            15            // If remainder is 0, we found the smallest multiple.16            if (remainder == 0) {17                return length;18            }19        }20        21        // This part should be unreachable if k is not divisible by 2 or 5.22        return -1;23    }24}

Complexity

Time

O(k). The loop runs at most `k` times. Each operation inside the loop (multiplication, addition, modulo) is a constant-time operation on standard integers. Therefore, the total time complexity is linear with respect to `k`.

Space

O(1). The algorithm uses only a few variables to store the current length and remainder, regardless of the size of `k`. The space used is constant.

Trade-offs

Pros

Extremely efficient in both time and space.
Avoids large number arithmetic and potential overflows.
Provides a complete and correct solution by handling all edge cases.

Cons

The proof of correctness relies on number theory concepts (modular arithmetic, Pigeonhole Principle), which might not be immediately obvious.

Solutions

Solution

1class Solution {2public3  int smallestRepunitDivByK(int k) {4    int n = 1 % k;5    for (int i = 1; i <= k; ++i) {6      if (n == 0) {7        return i;8      }9      n = (n * 10 + 1) % k;10    }11    return -1;12  }13}

1class Solution { public: int smallestRepunitDivByK ( int k ) { int n = 1 % k ; for ( int i = 1 ; i <= k ; ++ i ) { if ( n == 0 ) { return i ; } n = ( n * 10 + 1 ) % k ; } return - 1 ; } };

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

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem