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