leetcode
leetcode 901 ~ 950
可被 K 整除的最小整数

可被 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组成的数都可以表示为(10^n - 1)/ 9的形式,其中n是数字1的个数。进一步分析,数字1组成的数在模10运算下的余数总是1,因此如果k是2或5的倍数,即k在模10运算下的余数为0、2、4、5、6、8,这些数无法整除任何以1结尾的数(例如1, 11, 111, ...)。因此,如果k是2或5的倍数,则不存在由数字1组成的数能整除k。
🦆
在算法中通过使用模运算来避免大数处理的具体原理是什么?
在算法中,通过使用模运算可以有效避免生成和存储大数字。具体来说,每次迭代生成一个新的由1组成的数,我们只保留这个数对k的余数而不是数本身。这样做的原理是基于同余定理,即如果两个数a和b满足a % k == b % k,则a和b在除以k的时候有相同的余数。因此,算法只需要跟踪余数而不是实际的数字,从而大幅度减少了空间和计算需求。
🦆
为什么在判断余数已经在集合中出现过时,就可以确定不存在答案而返回-1?
在算法中使用集合来存储每次计算得到的余数。如果在某次迭代中发现新计算的余数已经在集合中,这意味着之前已经有一个相同的余数被计算过,而之后的迭代将会重复之前的模式,形成循环。由于余数开始循环,不会出现新的余数结果,也不可能达到余数为0的情况(即整除情况),因此可以判断出不存在一个全1的数能够被k整除,返回-1。
🦆
如果k的值非常大接近105,算法的性能表现如何?是否有优化的可能性?
当k的值非常大时,虽然每次迭代仅生成和比较余数,算法的时间复杂度主要取决于找到余数重复或生成余数0需要的迭代次数。这可能导致性能问题,尤其是在k值接近或等于上限105时。对于优化,可以考虑数学上更高级的方法来预测和跳过部分迭代,或者使用并行处理和优化数据结构来减少查找和存储操作的时间。但是,给定算法的基本逻辑和限制,主要的性能瓶颈在于必须逐一验证每个可能的余数,这限制了大幅度优化的空间。

相关问题