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
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;
}
}