Approach

# 前一個數字的餘數乘以 10 再加 1。
111 = 11 * 10 + 1;
111 = (1 * 10 + 1) * 10 + 1;

if k == 3 ; (((10 % 3 + 1) * 10) % 3 + 1) % 3 = 0
> 10的因數永遠無法找到(排除1)

# 根據鴿籠原理，
# 求餘數可能的值只有 0 ～ k - 1 這 k 個可能，做k + 1次這個過程餘數值至少會重複一次
# 如果沒有辦法在k次裡面遇到餘數為0的結果，繼續做也不會遇到。

Time Complexity

# n = digit of k
O(n)

Space Complexity

O(1)

Code

class Solution {
public:
    int smallestRepunitDivByK(int k) {
        if (k % 2 == 0 || k % 5 == 0) {
            return -1;
        }
        else {
            int sum = 1, cnt = 1;
            while (sum % k != 0) {
                sum %= k;
                sum *= 10;
                sum += 1;
                cnt++;
            }
            return cnt;
        }
    }
};