1015. 可被 K 整除的最小整数【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 模拟 + 同余

1. 📝 题目描述

• leetcode

给定正整数 k，你需要找出可以被 k 整除的、仅包含数字 1 的最 小 正整数 n 的长度。

返回 n 的长度。如果不存在这样的 n，就返回-1。

---

注意：n 可能不符合 64 位带符号整数。

---

示例 1：

输入：k = 1
输出：1
解释：最小的答案是 n = 1，其长度为 1。

示例 2：

输入：k = 2
输出：-1
解释：不存在可被 2 整除的正整数 n。

示例 3：

输入：k = 3
输出：3
解释：最小的答案是 n = 111，其长度为 3。

---

提示：

• 1 <= k <= 10^5

2. 🎯 s.1 - 模拟 + 同余

js] <<< ./solutions/1/1.c [c] <<< ./solutions/1/1.py [py

/**
 * @param {number} k
 * @return {number}
 */
var smallestRepunitDivByK = function (k) {
  if (k % 2 === 0 || k % 5 === 0) return -1
  let remainder = 0
  for (let len = 1; len <= k; len++) {
    remainder = (remainder * 10 + 1) % k
    if (remainder === 0) return len
  }
  return -1
}

• 时间复杂度：$O(k)$，最多遍历 $k$ 次
• 空间复杂度：$O(1)$，只使用了常数级别的额外空间

算法思路：

• 如果 k 是 2 或 5 的倍数，全 1 的数不可能被其整除，直接返回 -1
• 否则用余数递推：remainder = (remainder * 10 + 1) % k
• 根据鸽巢原理，余数最多有 k 个不同值，因此最多遍历 k 次必能找到答案