Problem

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 _thelength of _n. If there is no such n, return -1.

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

Examples

Example 1

1
2
3

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

Example 2

1
2
3

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

Example 3

1
2
3

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

Constraints

  • 1 <= k <= 10^5

Solution

Method 1 – Remainder Cycle Detection (Math, Hashing)

Intuition

We want the smallest number consisting only of 1’s that is divisible by k. Instead of constructing the number, we can keep track of the remainder when dividing by k as we “append” 1’s. If the remainder repeats, we are in a cycle and will never reach 0 (no such number exists).

Approach

  1. Start with remainder = 0.
  2. For each length from 1 to k (at most k steps), update remainder = (remainder * 10 + 1) % k.
  3. If remainder == 0, return the current length.
  4. If we reach k steps without finding remainder 0, return -1.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
public:
    int smallestRepunitDivByK(int k) {
        int rem = 0;
        for (int len = 1; len <= k; ++len) {
            rem = (rem * 10 + 1) % k;
            if (rem == 0) return len;
        }
        return -1;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution {
    public int smallestRepunitDivByK(int k) {
        int rem = 0;
        for (int len = 1; len <= k; ++len) {
            rem = (rem * 10 + 1) % k;
            if (rem == 0) return len;
        }
        return -1;
    }
}
1
2
3
4
5
6
7
8

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

Complexity

  • ⏰ Time complexity: O(k) — At most k steps, since remainders repeat after k steps.
  • 🧺 Space complexity: O(1) — Only a few variables are used.