Java 中能被 K 整除的最小整数问题

问题陈述

给定一个正整数 k。我们需要找到一个名为 n 的最小正整数，该整数能被 k 整除，并且 n 中的每个数字都只能是数字 1。整数 n 应由重复的数字 1 构成，重复一次或多次。任务是返回数字 n 的长度。但是，如果对于给定的 k 不存在这样的数字 n，我们可以返回 -1。

注意：数字 n 可能非常大，以至于无法放入 64 位有符号 整数中。因此，我们应该关注数字 n 的长度，而不是构造数字本身。

示例 1

输入: k = 7

输出 6

解释: 由数字 1 组成的最小能被 7 整除的数字是 111111。数字 111111 的长度是 6。因此，输出是 6。

示例 2

输入: k = 11

输出 2

解释: 由数字 1 组成的最小能被 11 整除的数字是 11。数字 11 的长度是 2。

示例 3

输入 5

输出 -1

解释: 不存在由数字 1 组成的、能被 5 整除的正整数 n，因为所有这样的数字都以 1 结尾，不能被 5 整除。

方法：使用暴力破解

解决此问题的最简单方法是使用暴力破解方法。以下是解决问题的步骤。

步骤 1: 检查 k 是否能被 2 或 5 整除。如果是，则返回 -1。

步骤 2: 创建一个名为 num 的变量，并用字符串 "1" 进行初始化。

步骤 3: 创建一个名为 length 的变量并初始化为 1。

步骤 4: 当 num 所代表的数字不能被 k 整除时，执行以下操作：

步骤 4.1: 将字符 '1' 追加到 num 中，以创建下一个重复数。

步骤 4.2: 将 length 增加 1。

步骤 5: 检查 num 的长度是否超过 18 位。如果是，则返回 -1。

步骤 6: 使用 模运算 (num % k == 0) 检查 num 所代表的数字是否能被 k 整除。

步骤 6.1: 如果能整除，则退出循环。

步骤 7: 返回能被 k 整除的连续 1 的最小长度。否则，如果不存在这样的重复数，则返回 -1。

输出

 
The Smallest integer divisible by 7 is : 6
The Smallest integer divisible by 11 is : 2
The Smallest integer divisible by 5 is : -1   

复杂度分析

时间复杂度为 O(n²)，其中 n 是连续 1 的序列的长度，因为在每次迭代中，我们都将一个 1 追加到字符串中并执行一次可被 k 整除的检查，这需要 O(n) 时间，而我们对 n 次迭代执行此操作。

空间复杂度为 O(n)，因为字符串 num 的长度在每次迭代中会增加一位数字，需要与连续 1 的序列长度成比例的空间。

方法：使用贪心算法

暴力破解方法对于大值来说太慢了。我们应该尝试使用贪心算法，并结合数学运算来避免直接构造数字，而不是使用字符串操作。解决问题的步骤如下。

步骤 1: 最初，检查 k 是否等于 1。如果是，则返回 1。

步骤 2: 初始化 len = 1 来跟踪最小有效数字的长度。

步骤 3: 创建一个名为 rest 的变量来存储除法的余数。

步骤 4: 创建 StringBuilder 类来存储数字的各位。

步骤 5: 循环直到找到一个有效数字

步骤 5.1: 设置一个名为 match 的标志为 false，用于跟踪是否找到有效数字。

步骤 6: 遍历从 0 到 9 的数字以查找有效数字

步骤 6.1: 检查该数字乘以 K 并与当前余数组合时，是否形成一个有效的重复数模式。

步骤 6.2: 如果找到有效数字

步骤 6.2.1: 更新 rest 以存储下一步的余数。

步骤 6.2.2: 将有效数字追加到数字中。

步骤 6.2.3: 将 match 设置为 true 并中断循环。

步骤 7: 如果在迭代中未找到有效数字，则返回 -1。

步骤 8: 一旦找到有效数字，则返回其长度 (len)。

输出

 
The Smallest integer divisible by 7 is : 6
The Smallest integer divisible by 11 is : 2
The Smallest integer divisible by 5 is : -1   

复杂度分析

程序 takes O(k) time because, in the worst case, it iterates up to k times. For each iteration, an inner loop runs at most 10 times by taking O(1) time. It also takes o(1) time to check digits and update the remainder. Thus making the overall time complexity of O(k). The space complexity is also O(K) because the StringBuilder stores at most K digits.

方法：使用广度优先搜索

贪心算法在每一步都遍历所有可能的数字，这是低效且复杂的。我们可以使用 BFS 方法找到最短的能被 k 整除的整数。观察以下步骤来解决问题。

步骤 1: 检查 k 是否能被 2 或 5 整除。如果能，则返回 -1。

步骤 2: 创建一个队列来跟踪我们在构造仅由 1 组成的数字时的余数。

步骤 3: 创建一个集合来存储我们已经访问过的余数，以防止循环和无限循环。

步骤 4: 用 1 % k 的余数 (即 1) 初始化队列，因为第一个数字只是 1。

步骤 5: 将变量 lnth 设置为 1，因为第一个数字的长度为 1 (即 '1')。

步骤 6: 当队列不为空时

步骤 6.1: 从队列中出队一个名为 remainder 的元素。

步骤 6.2: 检查余数是否为 0。如果是，则找到当前由“1”组成的能被 k 整除的数字，返回当前长度。

步骤 6.3: 如果余数之前未被访问过 (即不在集合中)

步骤 6.3.1: 将余数标记为已访问，将其添加到集合中。

步骤 6.3.2: 计算将另一个 '1' 追加到数字时的新的余数，即 (remainder * 10 + 1) % k。

步骤 6.3.3: 将此新余数添加到队列中，并将长度加 1。

步骤 7: 如果队列变空但未找到余数 0，则返回 -1，表示不存在有效数字。

输出

 
The Smallest integer divisible by 7 is : 6
The Smallest integer divisible by 11 is : 2
The Smallest integer divisible by 5 is : -1   

复杂度分析

时间复杂度为 O(k)，因为队列最多存储 k 个余数，并且每个余数都只处理一次。对于每个余数，我们执行常数时间的操作：检查其是否为零、将其添加到访问集以及计算下一个余数，所有这些都耗时 O(1)。空间复杂度为 O(k)，因为需要空间来在队列和访问集中存储多达 k 个余数。

方法：使用哈希表

BFS 方法需要额外的空间来存储已访问的余数。因此，让我们通过使用 HashMap 来存储余数并确保我们不会无限循环来对其进行优化。以下步骤将指导我们解决问题。

步骤 1: 检查 k 是否能被 2 或 5 整除。如果是，则返回 -1。

步骤 2: 初始化变量 num = 1 % k 来存储 1 除以 k 时的余数，以及长度为 1 来存储序列中的数字位数。

步骤 3: 循环以查找能被 k 整除的最小数字

步骤 3.1: 当 num 不为 0 时

步骤 3.1.1: 将 num 乘以 10 并加 1 来扩展序列。

步骤 3.1.2: 更新 num = (num * 10 + 1) % k 来存储新的余数。

步骤 3.1.3: 将 length 增加 1。

步骤 4: 当 num 变为 0 时，返回 length 作为能被 k 整除的最小数字的长度。

输出

 
The Smallest integer divisible by 7 is : 6
The Smallest integer divisible by 11 is : 2
The Smallest integer divisible by 5 is : -1   

复杂度分析

程序 takes O(k) time because the remainder, named num, can take at most k different values from 0 to k – 1 before either finding a divisible number or repeating zero. Each iteration performs a constant time modulo operation. Therefore, the overall time complexity is O(k). The space complexity is O(1) because only a few integer variables are used.

方法：使用模余数

前一种方法仍然需要空间来存储余数。我们可以只存储当前步骤的当前余数，而不是存储过去的余数，使用模余数方法。可以使用以下步骤来解决问题。

步骤 1: 创建一个名为 hm 的 HashMap 来存储余数并跟踪循环。

步骤 2: 初始化一个名为 r 的变量作为余数，初始值为 0，它将存储仅由数字 1 组成的数字除以 k 时的余数。

步骤 3: 初始化一个名为 c 的变量，初始值为 0，它将存储重复数中数字 (1) 的数量。

步骤 4: 只要余数 r 不为 0 或数字计数 c 仍为 0，则进行迭代

步骤 5: 在每次循环迭代中，通过更新余数 r 来将 '1' 追加到数字

步骤 5.1: 计算 r = r % k 以获得除法后的余数。

步骤 5.2: 如果在 HashMap 中找到余数 r，则检测到循环，因此返回 -1。

步骤 5.3: 否则，将 r 存储在 HashMap 中。

步骤 5.4: 增加 c 的计数以存储连续 1 的序列中的数字数量。

步骤 6: 如果找到一个能被 k 整除的有效连续 1 的序列，则返回 c，即其长度。

步骤 6.1: 如果检测到循环，则返回 -1。

输出

 
The Smallest integer divisible by 7 is : 6
The Smallest integer divisible by 11 is : 2
The Smallest integer divisible by 5 is : -1   

复杂度分析

此方法的时间复杂度为 O(k)，因为在最坏情况下，我们可能需要检查多达 k 个不同的余数，才能找到一个可整除的数字或检测到循环。空间复杂度为 O(k)，因为它将余数存储在集合中以跟踪循环并避免无限循环。