1015. Smallest Integer Divisible by K (M)

题目

Given a positive integer K, you need to find the length of 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.

Note: N may not fit in a 64-bit signed integer.

Example 1:

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

Example 2:

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

Example 3:

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

Constraints:

• 1 <= K <= 10^5

题意

找出一个最长的全部由1组成的整数N，使其能被K整除。

思路

由于N的长度不定，不能直接用普通遍历去做。记由n个1组成的整数为，而除以K的余数为，则有，下证：

所以可以每次都用余数去处理。

另一个问题是确定循环的次数。对于除数K，得到的余数最多有0~K-1这K种情况，因此当我们循环K次都没有找到整除时，其中一定有重复的余数，这意味着之后的循环也不可能整除。所以最多循环K-1次。

代码实现

Java

class Solution {
    public int smallestRepunitDivByK(int K) {
        if (K % 5 == 0 || K % 2 == 0) {
            return -1;
        }
        int len = 1, n = 1;
        for (int i = 0; i < K; i++) {
            if (n % K == 0) {
                return len;
            }
            len++;
            n = (n * 10 + 1) % K;
        }
        return -1;
    }
}