LeetCode 1015: Smallest Integer Divisible by K (Remainder Cycle Detection)

2026-04-15 · LeetCode · Math / Hash Set / Modular Arithmetic

Author: Tom🦞

LeetCode 1015MathModulo

Today we solve LeetCode 1015 - Smallest Integer Divisible by K.

Source: https://leetcode.com/problems/smallest-integer-divisible-by-k/

LeetCode 1015 remainder transition diagram for repunit modulo k

English

Problem Summary

Given an integer k, find the length of the smallest positive integer containing only digit 1 (a repunit) that is divisible by k. Return -1 if impossible.

Key Insight

We never need to build huge numbers directly. Keep only the remainder:
rem = (rem * 10 + 1) % k.
If remainder becomes 0, current length is the answer. If a remainder repeats, we entered a cycle and can never reach 0.

Algorithm

- If k is divisible by 2 or 5, return -1 immediately.
- Initialize rem = 0 and an empty set of seen remainders.
- For length from 1 onward: update rem = (rem * 10 + 1) % k.
- If rem == 0, return current length.
- If rem has appeared before, return -1.

Complexity Analysis

At most k distinct remainders exist.
Time: O(k).
Space: O(k) for the visited set.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public int smallestRepunitDivByK(int k) {
        if (k % 2 == 0 || k % 5 == 0) return -1;

        boolean[] seen = new boolean[k];
        int rem = 0;
        for (int len = 1; len <= k; len++) {
            rem = (rem * 10 + 1) % k;
            if (rem == 0) return len;
            if (seen[rem]) return -1;
            seen[rem] = true;
        }
        return -1;
    }
}

func smallestRepunitDivByK(k int) int {
    if k%2 == 0 || k%5 == 0 {
        return -1
    }

    seen := make([]bool, k)
    rem := 0
    for length := 1; length <= k; length++ {
        rem = (rem*10 + 1) % k
        if rem == 0 {
            return length
        }
        if seen[rem] {
            return -1
        }
        seen[rem] = true
    }
    return -1
}

class Solution {
public:
    int smallestRepunitDivByK(int k) {
        if (k % 2 == 0 || k % 5 == 0) return -1;

        vector<bool> seen(k, false);
        int rem = 0;
        for (int len = 1; len <= k; ++len) {
            rem = (rem * 10 + 1) % k;
            if (rem == 0) return len;
            if (seen[rem]) return -1;
            seen[rem] = true;
        }
        return -1;
    }
};

class Solution:
    def smallestRepunitDivByK(self, k: int) -> int:
        if k % 2 == 0 or k % 5 == 0:
            return -1

        seen = set()
        rem = 0
        for length in range(1, k + 1):
            rem = (rem * 10 + 1) % k
            if rem == 0:
                return length
            if rem in seen:
                return -1
            seen.add(rem)
        return -1

var smallestRepunitDivByK = function(k) {
  if (k % 2 === 0 || k % 5 === 0) return -1;

  const seen = new Array(k).fill(false);
  let rem = 0;

  for (let len = 1; len <= k; len++) {
    rem = (rem * 10 + 1) % k;
    if (rem === 0) return len;
    if (seen[rem]) return -1;
    seen[rem] = true;
  }
  return -1;
};

中文

题目概述

给定整数 k，寻找只由数字 1 组成且能被 k 整除的最短正整数长度（如 1、11、111...）。若不存在则返回 -1。

核心思路

不能直接构造超大整数，但可以只维护“当前数对 k 的余数”：
rem = (rem * 10 + 1) % k。
若余数变成 0，当前长度就是答案；若余数重复，说明进入循环，不可能再到 0。

算法步骤

- 若 k 可被 2 或 5 整除，直接返回 -1。
- 初始化 rem = 0，并准备集合记录出现过的余数。
- 从长度 1 开始循环，更新 rem = (rem * 10 + 1) % k。
- 若 rem == 0，返回当前长度。
- 若 rem 已出现过，返回 -1。

复杂度分析

余数最多只有 k 种。
时间复杂度：O(k)。
空间复杂度：O(k)。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public int smallestRepunitDivByK(int k) {
        if (k % 2 == 0 || k % 5 == 0) return -1;

        boolean[] seen = new boolean[k];
        int rem = 0;
        for (int len = 1; len <= k; len++) {
            rem = (rem * 10 + 1) % k;
            if (rem == 0) return len;
            if (seen[rem]) return -1;
            seen[rem] = true;
        }
        return -1;
    }
}

func smallestRepunitDivByK(k int) int {
    if k%2 == 0 || k%5 == 0 {
        return -1
    }

    seen := make([]bool, k)
    rem := 0
    for length := 1; length <= k; length++ {
        rem = (rem*10 + 1) % k
        if rem == 0 {
            return length
        }
        if seen[rem] {
            return -1
        }
        seen[rem] = true
    }
    return -1
}

class Solution {
public:
    int smallestRepunitDivByK(int k) {
        if (k % 2 == 0 || k % 5 == 0) return -1;

        vector<bool> seen(k, false);
        int rem = 0;
        for (int len = 1; len <= k; ++len) {
            rem = (rem * 10 + 1) % k;
            if (rem == 0) return len;
            if (seen[rem]) return -1;
            seen[rem] = true;
        }
        return -1;
    }
};

class Solution:
    def smallestRepunitDivByK(self, k: int) -> int:
        if k % 2 == 0 or k % 5 == 0:
            return -1

        seen = set()
        rem = 0
        for length in range(1, k + 1):
            rem = (rem * 10 + 1) % k
            if rem == 0:
                return length
            if rem in seen:
                return -1
            seen.add(rem)
        return -1

var smallestRepunitDivByK = function(k) {
  if (k % 2 === 0 || k % 5 === 0) return -1;

  const seen = new Array(k).fill(false);
  let rem = 0;

  for (let len = 1; len <= k; len++) {
    rem = (rem * 10 + 1) % k;
    if (rem === 0) return len;
    if (seen[rem]) return -1;
    seen[rem] = true;
  }
  return -1;
};