problemmediumalgorithmsleetcode-1015leetcode 1015leetcode1015

Smallest Integer Divisible by K

MediumUpdated: Aug 2, 2025
Practice on:
LeetCode

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

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^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

C++
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;
    }
};
Java
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;
    }
}
Python
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.

Comments