原文链接: https://leetcode-cn.com/problems/smallest-integer-divisible-by-k

英文原文

Given a positive integer k, you need to find the length of the smallest positive integer n such that n is divisible by k, and n only contains the digit 1.

Return the length of n. If there is no such n, return -1.

Note: n may not fit in a 64-bit signed integer.

 

Example 1:

Input: k = 1
Output: 1
Explanation: The smallest answer is n = 1, which has length 1.

Example 2:

Input: k = 2
Output: -1
Explanation: There is no such positive integer n divisible by 2.

Example 3:

Input: k = 3
Output: 3
Explanation: The smallest answer is n = 111, which has length 3.

 

Constraints:

• 1 <= k <= 105

中文题目

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

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

 

示例 1：

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

示例 2：

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

示例 3：

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

 

提示：

• 1 <= K <= 10^5

通过代码

高赞题解

正常思路

通过以下代码，我们可以计算出的答案。首先我们检查x是否是K的倍数，如果不是，我们将其乘10加1。

while (x % K != 0) {
    x = x * 10 + 1;
}

优化方案

容易想到，反复乘10加1很快就会超出int能表示的范围。

对于任意整数$x > 0$，存在非负整数$p$和$q$，使得$x = pK + q$。例如，$x = 2$，$K = 5$时，可以令$p = 0$，$q = 2$。又例如，$x = 29$，$K = 7$时，可以令$p = 4$，$q = 1$。

我们在计算答案时，使用了以下公式：

$$
x_{i+1} = 10 x_i + 1
$$

请注意代码与公式的不同。代码中，我们把$x_{i+1}$的值又保存在了$x_i$的位置，覆盖了其原来的值。为了使得证明过程更加清晰明了，我们在公式中体现这种区别。

我们将前一条公式代入，因此有了：

$$
10 x_i + 1 = 10 (pK + q) + 1 = 10 pK + 10 q + 1
$$

由于等号两边相等，那么在两边分别对$K$取余，其结果也应该相等。

$$
(10 x_i + 1) % K = (10 pK + 10 q + 1) % K
$$

观察等式右侧，有一项$10 pK$，由于它是$K$的倍数，因此无论$p$为何值，这一项都不会影响最终结果，因此将它去掉，得到：

$$
(10 x_i + 1) % K = (10 q + 1) % K
$$

由于$x = pK + q$，我们能够推出$x % K = q$，带入上式：

$$
(10 x_i + 1) % K = (10 (x_i % K) + 1) % K
$$

再看一眼上一节中的代码：

while (x % K != 0) {
    x = x * 10 + 1;
}

最后的公式告诉我们，x * 10 + 1和(x % K) * 10 + 1在后续判断x % K != 0时是没有任何区别的。因此我们可以将代码改成：

while (x % K != 0) {
    x = x % K;
    x = x * 10 + 1;
}

这样就可以避免x超范围了。

数学证明

上述算法有没有什么漏洞呢？我们来分析一下。

必要性

设上述程序执行完x = x % K这一句后，$x$的值（或者称为状态）为$S$。

那么一共有多少种$S$呢？由于刚刚执行完x = x % K，所以$x$是不可能大于等于$K$的，因此$S$种类数不会超过$K$。

那么求解答案的过程中，可不可以重复经过某个状态$S_i$呢？不可以，因为相同的$x$值必然在后续的x = x * 10 + 1等语句中产生相同的结果，程序则必然陷入死循环。

那么，什么样的$K$会使程序重复经过某个状态$S_i$呢？

程序求解过程中，设程序经历了如下状态序列：$S_1$，$S_2$，$S_3$，$\dots$，$S_i$，$\dots$，$S_j$，$\dots$，$S_n$。

假设，存在$S_i = S_j$，也就是：

$$
(10 S_{i-1} + 1) % K = (10 S_{j-1} + 1) % K
$$

让我们把取余操作去掉，于是等式变成了：

$$
10 S_{i-1} + 1 = 10 S_{j-1} + 1 + a K
$$

其中，$a$是一个能使等式成立的值，类似上面的$p$、$q$。我们整理一下这个等式（假设$S_{i-1} > S_{j-1}$）：

$$
S_{i-1} - S_{j-1} = \frac{aK}{10}
$$

$a$的取值范围是多少呢？$S_{i-1}$和$S_{j-1}$都是小于$K$的（因为他们也刚经历了x = x % K语句），因此$0 < 10(S_{i-1} - S_{j-1}) < 10K$，所以$0 < a < 10$。

使用一个大于0，小于10的整数，如何消除分母上的10，使得$\frac{aK}{10}$成为一个整数呢？那就只有$2 \times 5 = 10$这条路了。

因此只有$K$是2或5的倍数时，我们才能找到一个$a$的值，使$\frac{aK}{10}$成为一个整数，使$S_{i-1} - S_{j-1} = \frac{aK}{10}$成立，使$S_i = S_j$成立，最终程序会死循环。此时我们可以得到结论：假设陷入了死循环，$K$只能是2或5的倍数。

充分性

我们回到这个关键的式子：

$$
(10 S_{i-1} + 1) % K = (10 S_{j-1} + 1) % K
$$

忘记证明必要性时的那一大堆文字吧，回归最简单的思考。大家看看上面的式子，$K = 2$或者$K = 5$的时候上面的式子必然成立，因为此时$10 S_{i-1}$和$10 S_{j-1}$一定被$K$整除。充分性得证，如果$K$是2或5的倍数，则一定陷入死循环。

Java代码

结合必要性和充分性，我们可以得到结论：程序陷入死循环，当且仅当$K$是2或5的倍数。

所以，最终的程序如下所示：

public static int smallestRepunitDivByK(int K) {
    if (K % 2 == 0 || K % 5 == 0) {
        return -1;
    }
    int temp = 1;
    int len = 1;
    while (temp % K != 0) {
        temp = temp % K;
        temp = temp * 10 + 1;
        len += 1;
    }
    return len;
}

感谢@dan-huang-jiang-xing-ren在评论中指出第一版题解的问题！

统计信息

通过次数	提交次数	AC比率
5127	14357	35.7%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言