Smallest Integer Divisible by K

medium math hash map

Problem

Return the length of the smallest positive integer made only of 1s that is divisible by k. If none exists, return -1.

Inputk = 3

Output3

Track remainder r; r = (10r + 1) mod k. r repeats ⇒ no solution (k divisible by 2 or 5).

def smallestRepunitDivByK(k):
    if k % 2 == 0 or k % 5 == 0: return -1
    r, length = 0, 0
    for _ in range(k):
        r = (r * 10 + 1) % k
        length += 1
        if r == 0: return length
    return -1

function smallestRepunitDivByK(k) {
  if (k % 2 === 0 || k % 5 === 0) return -1;
  let r = 0, length = 0;
  for (let i = 0; i < k; i++) {
    r = (r * 10 + 1) % k;
    length++;
    if (r === 0) return length;
  }
  return -1;
}

class Solution {
    public int smallestRepunitDivByK(int k) {
        if (k % 2 == 0 || k % 5 == 0) return -1;
        int r = 0, length = 0;
        for (int i = 0; i < k; i++) {
            r = (r * 10 + 1) % k;
            length++;
            if (r == 0) return length;
        }
        return -1;
    }
}

int smallestRepunitDivByK(int k) {
    if (k % 2 == 0 || k % 5 == 0) return -1;
    int r = 0, length = 0;
    for (int i = 0; i < k; i++) {
        r = (r * 10 + 1) % k;
        length++;
        if (r == 0) return length;
    }
    return -1;
}

Explanation

We want the shortest number made only of 1s (1, 11, 111, ...) that k divides. The numbers grow huge fast, so instead of building them we only track each one's remainder mod k.

First a quick filter: if k is divisible by 2 or 5, no all-1s number can ever be a multiple (those end in 1, never even or ending in 0/5), so we return -1 right away.

Otherwise we build the remainder step by step. Appending a 1 to a number means new = old * 10 + 1, so the remainder updates as r = (r * 10 + 1) % k. The first time r becomes 0, the current length is our answer.

There are only k possible remainders, so after at most k steps a remainder must repeat — meaning if we haven't hit 0 by then, we never will.

Example: k = 3. r = 1, then (1·10+1)%3 = 2, then (2·10+1)%3 = 0 at length 3. Indeed 111 = 3 · 37, so the answer is 3.

Time: O(k) Space: O(1)