LeetCode Solutions
1015. Smallest Integer Divisible by K
Time: $O(k)$ Space: $O(k)$
class Solution {
public:
int smallestRepunitDivByK(int K) {
if (K % 10 != 1 && K % 10 != 3 && K % 10 != 7 && K % 10 != 9)
return -1;
unordered_set<int> seen;
int N = 0;
for (int length = 1; length <= K; ++length) {
N = (N * 10 + 1) % K;
if (N == 0)
return length;
if (seen.count(N))
return -1;
seen.insert(N);
}
return -1;
}
};
class Solution {
public int smallestRepunitDivByK(int K) {
if (K % 10 != 1 && K % 10 != 3 && K % 10 != 7 && K % 10 != 9)
return -1;
Set<Integer> seen = new HashSet<>();
int N = 0;
for (int length = 1; length <= K; ++length) {
N = (N * 10 + 1) % K;
if (N == 0)
return length;
if (seen.contains(N))
return -1;
seen.add(N);
}
return -1;
}
}
class Solution:
def smallestRepunitDivByK(self, K: int) -> int:
if K % 10 not in {1, 3, 7, 9}:
return -1
seen = set()
N = 0
for length in range(1, K + 1):
N = (N * 10 + 1) % K
if N == 0:
return length
if N in seen:
return -1
seen.add(N)
return -1