Given a positive integer K, you need find the **smallest** positive integer N such that N is divisible by K, and N only contains the digit **1**.

Return the length of N. If there is no such N, return -1.

Input:1Output:1Explanation:The smallest answer is N = 1, which has length 1.

Input:2Output:-1Explanation:There is no such positive integer N divisible by 2.

Input:3Output:3Explanation:The smallest answer is N = 111, which has length 3.

- 1 <= K <= 10^5

Solution:

class Solution { public int smallestRepunitDivByK(int K) { if (K % 2 == 0 || K % 5 == 0) { return -1; } // You can update r = r % K once r > K. // Suppose r = (aK + b) when r > K, next r supposed to be 10r+1 = 10aK + 10b + 1. Since 10aK is divisible by K, we just need to consider 10b + 1. // b is r % K, so we can update r = r % K. int r = 0; for (int n = 1; n <= K + 1; n ++) { r = (10 * r + 1) % K; if (r == 0) return n; } return -1; } }