LC.P1015[可被K整除的最小整数]

方法一:Set遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public int smallestRepunitDivByK(int k) {
if (k % 2 == 0 || k % 5 == 0) return -1;
int x = 1 % k, cnt = 1;
Set<Integer> set = new HashSet<>();
while (x > 0) {
x = (x * 10 + 1) % k;
if (set.contains(x)) return -1;
set.add(x);
++cnt;
}
return cnt;
}
}
  • 时间复杂度:$O(k)$
  • 空间复杂度:$O(k)$

方法二:数学

1
2
3
4
5
6
7
8
9
10
class Solution {
public int smallestRepunitDivByK(int k) {
if (k % 2 == 0 || k % 5 == 0) return -1;
int x = 1 % k;
for (int i = 1; ; ++i) {
if (x == 0) return i;
x = (x * 10 + 1) % k;
}
}
}
  • 时间复杂度:$O(k)$
  • 空间复杂度:$O(1)$