# 1015. Smallest Integer Divisible by K

• Time: $O(k)$
• Space: $O(k)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 class Solution { public: int smallestRepunitDivByK(int K) { if (K % 10 != 1 && K % 10 != 3 && K % 10 != 7 && K % 10 != 9) return -1; unordered_set 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; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 class Solution { public int smallestRepunitDivByK(int K) { if (K % 10 != 1 && K % 10 != 3 && K % 10 != 7 && K % 10 != 9) return -1; Set 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; } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 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