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.

Example 1:

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

Example 2:

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

Example 3:

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

Note:

1 <= K <= 10^5

解题思路

需要迭代的数字为：1, 11, 111, 1111, 11111, ...，又根据公式
(10 * n + 1) % K = (10 * (n % K) + 1) % K，得出迭代方程为：n = (n * 10 + 1) % K。

实现代码

// Runtime: 2 ms, faster than 58.32% of Java online submissions for Smallest Integer Divisible by K.
// Memory Usage: 31.8 MB, less than 100.00% of Java online submissions for Smallest Integer Divisible by K.
class Solution {
    public int smallestRepunitDivByK(int K) {
        for (int i = 1, n = 0; i <= K; i++) {
            n = (n * 10 + 1) % K;
            if (n == 0) {
                return i;
            }
        }
        return -1;
    }
}