Medium

题目描述

给定一个正整数 k。

找到能被 k 整除且只由数字 1 组成的最小整数 n（例如，1、11、111 等）。

返回一个整数，表示 n 的十进制表示中的位数。如果不存在这样的 n，返回 -1。

示例 1:

输入: k = 3
输出: 3
解释: n = 111，因为 111 能被 3 整除，但 1 和 11 不能。n = 111 的长度是 3。

示例 2:

输入: k = 7
输出: 6
解释: n = 111111。n = 111111 的长度是 6。

示例 3:

输入: k = 2
输出: -1
解释: 不存在能被 2 整除的有效 n。

约束条件:

  • 2 <= k <= 10^5

提示:

  • 注意 n % k 应该等于 0
  • 使用只包含模 k 的运算逐位构建数字。从余数 rem = 1 % k 开始。重复更新 rem = (rem * 10 + 1) % k，同时计算已添加了多少个 1
  • 继续直到 rem == 0 或余数重复（这表示存在循环且不存在这样的 n）

解题思路

这道题的核心思想是模拟构建全1数字的过程，利用模运算来避免大数运算。

数学观察：

  1. 全1数字可以表示为：1、11、111、1111…，分别是1个1、2个1、3个1…
  2. 我们需要找到最小的n位全1数能被k整除
  3. 由于数字可能很大，我们不能直接计算，需要利用模运算的性质

算法思路：

  1. 从1位全1数字开始，逐步增加位数
  2. 使用模运算来跟踪当前数字对k的余数：(previous_remainder * 10 + 1) % k
  3. 如果余数为0，说明找到了答案
  4. 如果余数重复出现，说明进入了循环，不存在解

关键点：

  • 如果k包含因子2或5，则不可能有全1倍数（因为全1数都是奇数且不能被5整除）
  • 使用哈希表记录出现过的余数，检测循环

算法步骤：

  1. 初始化余数为1
  2. 逐步构建更长的全1数字，更新余数
  3. 记录已见过的余数，避免无限循环
  4. 当余数为0时返回位数，当检测到循环时返回-1

代码实现

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

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

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

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

复杂度分析

复杂度类型大小说明
时间复杂度O(k)最多需要k次迭代，因为余数的可能值为0到k-1
空间复杂度O(k)哈希表最多存储k个不同的余数值