Medium

题目描述

给定正整数 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

提示：

  • 11111 = 1111 * 10 + 1
  • 我们只需要存储模 K 的余数。
  • 如果我们从未得到余数 0，为什么会发生这种情况，我们如何知道？

解题思路

这道题要求找到只包含数字1且能被k整除的最小正整数的长度。

核心思路： 我们可以构造形如1、11、111、1111…的数列，逐步检查是否能被k整除。关键观察是：

  • 1 % k
  • 11 % k = (1 * 10 + 1) % k = ((1 % k) * 10 + 1) % k
  • 111 % k = (11 * 10 + 1) % k = ((11 % k) * 10 + 1) % k

算法步骤：

  1. 如果k能被2或5整除（除了k=5的特殊情况），那么不存在解，因为只含1的数不可能被2或5整除
  2. 从余数1开始，每次计算 remainder = (remainder * 10 + 1) % k
  3. 如果余数变为0，说明找到了答案
  4. 如果余数重复出现，说明进入循环，不存在解

优化分析：

  • 使用哈希集合记录出现过的余数，避免无限循环
  • 根据鸽笼原理，最多k-1个不同的非零余数，所以最多迭代k次

时间复杂度： O(k)
空间复杂度： O(k)

代码实现

class Solution {
public:
    int smallestRepunitDivByK(int k) {
        if (k % 2 == 0 || k % 5 == 0) {
            return -1;
        }
        
        unordered_set<int> seen;
        int remainder = 1;
        int length = 1;
        
        while (remainder % k != 0) {
            if (seen.count(remainder)) {
                return -1;
            }
            seen.insert(remainder);
            remainder = (remainder * 10 + 1) % k;
            length++;
        }
        
        return length;
    }
};

class Solution:
    def smallestRepunitDivByK(self, k: int) -> int:
        if k % 2 == 0 or k % 5 == 0:
            return -1
        
        seen = set()
        remainder = 1
        length = 1
        
        while remainder % k != 0:
            if remainder in seen:
                return -1
            seen.add(remainder)
            remainder = (remainder * 10 + 1) % k
            length += 1
        
        return length

public class Solution {
    public int SmallestRepunitDivByK(int k) {
        if (k % 2 == 0 || k % 5 == 0) {
            return -1;
        }
        
        HashSet<int> seen = new HashSet<int>();
        int remainder = 1;
        int length = 1;
        
        while (remainder % k != 0) {
            if (seen.Contains(remainder)) {
                return -1;
            }
            seen.Add(remainder);
            remainder = (remainder * 10 + 1) % k;
            length++;
        }
        
        return length;
    }
}

var smallestRepunitDivByK = function(k) {
    if (k % 2 === 0 || k % 5 === 0) return -1;
    
    let remainder = 0;
    for (let length = 1; length <= k; length++) {
        remainder = (remainder * 10 + 1) % k;
        if (remainder === 0) return length;
    }
    
    return -1;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(k) - 最多迭代k次，每次操作为常数时间
空间复杂度O(k) - 哈希集合最多存储k-1个余数