可被 K 整除的最小整数
难度:
标签:
题目描述
代码结果
运行时间: 32 ms, 内存: 19.9 MB
/*
思路:
使用Java Stream API实现上述逻辑,但由于Stream不擅长处理循环依赖的状态,这里使用IntStream的iterate方法模拟循环。
通过生成无限流来实现上述的寻找过程。
需要注意在无限流中限制搜索的长度以防止无限循环。
*/
import java.util.stream.IntStream;
public class Solution {
public int smallestRepunitDivByK(int k) {
if (k % 2 == 0 || k % 5 == 0) return -1;
int[] result = new int[1];
result[0] = 1;
return IntStream.iterate(1, length -> {
result[0] = (result[0] % k) * 10 + 1;
return length + 1;
}).filter(length -> result[0] % k == 0).findFirst().orElse(-1);
}
}
解释
方法:
此题解采用模拟方法以寻找由数字1组成的可以被k整除的最小正整数n。首先,对于任何由1组成的整数n,可以表示为如111...1(n个1),也可以表示为数字序列。该算法通过计算模k的余数来避免处理过大的整数。如果k为1,直接返回1因为1可以被1整除。如果k是2或5的倍数,那么不可能存在全1的数字能被k整除,因此返回-1。接着,使用一个集合来存储出现过的余数,从而检测循环。从1开始,逐步增加1的个数,计算每次形成的数模k的余数。如果余数为0,则当前的数就是答案。如果余数已经在集合中出现过,说明开始循环,不存在答案,返回-1。
时间复杂度:
O(k)
空间复杂度:
O(k)
代码细节讲解
🦆
为什么当k为2或5的倍数时,就可以直接判断不存在由数字1组成的数能被k整除?
▷🦆
在算法中通过使用模运算来避免大数处理的具体原理是什么?
▷🦆
为什么在判断余数已经在集合中出现过时,就可以确定不存在答案而返回-1?
▷🦆
如果k的值非常大接近105,算法的性能表现如何?是否有优化的可能性?
▷