题目描述

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

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

样例

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

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

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

注意

• 1 <= K <= 10^5

算法

(暴力枚举) $O(K)$

1. 从 1 开始枚举 N 的长度，在枚举过程中，每次添加一个 1 之后，重新计算出当前的余数 c，之后再继续用 c 乘 10 加 1 继续尝试。
2. 如果枚举过程中 c 重复出现，则说明答案不存在。如果 c 为 0，则说明找到了可以被 K 整除的数字。

时间复杂度

• 最多遍历 K 个余数，故最多枚举 K 次就知道答案存在或者不存在，时间复杂度为 $O(K)$。

空间复杂度

• 需要记录余数是否出现过，故空间复杂度为 $O(K)$。

C++ 代码

class Solution {
public:
    int smallestRepunitDivByK(int K) {
        if (K == 1)
            return 1;
        vector<bool> r(K, false);
        int c = 1, len = 1;
        r[c] = true;
        while (1) {
            c = (c * 10 + 1) % K;
            len++;
            if (c == 0)
                return len;
            else if (r[c]) {
                break;
            }
            r[c] = true;
        }
        return -1;
    }
};