1
class Solution {
2
  public int smallestRepunitDivByK(int k) {
3
    // if (k % 2 == 0 || k % 5 == 0) return -1;  // this trick may save a little time
4
    boolean[] hit = new boolean[k];
5
    int n = 0, ans = 0;
6
    while (true) { // at most k times, because 0 <= remainder < k
7
      ++ans;
8
      n =
9
          (n * 10 + 1)
10
              % k; // we only focus on whether to divide, so we only need to keep the remainder.
11
      if (n == 0) return ans; // can be divisible
12
      if (hit[n])
13
        return -1; // the remainder of the division repeats, so it starts to loop that means it
14
      // cannot be divisible.
15
      hit[n] = true;
16
    }
17
  }
18
}