Scale Engineer

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 <= 105

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.

import java.math.BigInteger; class Solution {    public int smallestRepunitDivByK(int k) {        if (k % 2 == 0 || k % 5 == 0) {            return -1;        }        BigInteger n = BigInteger.ONE;        BigInteger kBigInt = BigInteger.valueOf(k);        int length = 1;        // We only need to check up to k times due to the Pigeonhole Principle.        while (length <= k) {            if (n.mod(kBigInt).equals(BigInteger.ZERO)) {                return length;            }            n = n.multiply(BigInteger.TEN).add(BigInteger.ONE);            length++;        }        return -1; // Should not be reached if k is not divisible by 2 or 5    }}

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.

Solutions

class 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;  }}

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 →

Next problem