Smallest Integer Divisible by K

Description

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;
        for (int r = 0, n = 1; n <= K; ++n) {
            r = (10 * r + 1) % K;
            if (r == 0)
                return n;
        }
        return -1;
    }
};

If K is not divisible by 2 or 5, there must be a number N in the form 1111...1 such that K divides N and N $\le$ 111...1(K ones).

Proof: https://leetcode.com/problems/smallest-integer-divisible-by-k/discuss/260916/Proof%3A-we-only-need-to-consider-the-first-K-candidates-in-1-11-111-1111-...