LeetCode 1015 - Smallest Integer Divisible by K

https://leetcode.com/problems/smallest-integer-divisible-by-k/

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

https://leetcode.com/problems/smallest-integer-divisible-by-k/discuss/260875/Python-O(K)-with-Detailed-Explanations

For a given K, we evaluate 1 % K, 11 % K, 111 % K, ..., 11...1 (K '1's) % K.

• If any remainder is 0, then the current number is the smallest integer divisible by K.
• If none of the remainders is 0, then at some point, there must be some duplicate remainders (due to Pigeonhole principle), as the K remainders can only take at most K-1 different values excluding 0. In this case, no number with the pattern 1...1 is divisible by K. This is because once a remainder has a duplicate, the next remainder will be in a loop, as the previous remainder determines the next_mod, i.e., next_mod = (10 * prev_mod + 1) % K. Therefore, we will never see remainder==0.

A simple example is when K is 6. Once we see 1111 % 6 = 1, we immediately know 11111 % 6 will be 5, since 1 % 6 = 1 and 11 % 6 = 5. Therefore, there will be no such number that is divisible by 6.

• 1 % 6 = 1
• 11 % 6 = 5
• 111 % 6 = 3
• 1111 % 6 = 1
• 11111 % 6 = 5
• 111111 % 6 = 3

Also, it is easy to see that for any number whose last digit is not in {1, 3, 7, 9}, we should return -1.

class Solution:
    def smallestRepunitDivByK(self, K: int) -> int:
        if K % 10 not in {1, 3, 7, 9}: return -1
        mod, mod_set = 0, set()
        for length in range(1, K + 1):
            mod = (10 * mod + 1) % K
            if mod == 0: return length
            if mod in mod_set: return -1
            mod_set.add(mod)
        return -1

https://leetcode.com/problems/smallest-integer-divisible-by-k/discuss/260852/JavaC%2B%2BPython-O(1)-Space-with-Proves-of-Pigeon-Holes

Let's say the final result has N digits of 1.
If N exist, N <= K, just do a brute force check.
Also if K % 2 == 0, return -1, because 111....11 can't be even.
Also if K % 5 == 0, return -1, because 111....11 can't end with 0 or 5.

Explanation

For different N, we calculate the remainder of mod K.
It has to use the remainder for these two reason:

1. Integer overflow
2. The division operation for big integers, is NOT O(1), it's actually depends on the number of digits..

Prove

Why 5 is a corner case? It has a reason and we can find it.
Assume that N = 1 to N = K, if there isn't 111...11 % K == 0
There are at most K - 1 different remainders: 1, 2, .... K - 1.

So this is a pigeon holes problem:
There must be at least 2 same remainders.

Assume that,
f(N) ≡ f(M), N > M
f(N - M) * 10 ^ M ≡ 0
10 ^ M ≡ 0, mod K
so that K has factor 2 or factor 5.

Proof by contradiction，
If (K % 2 == 0 || K % 5 == 0) return -1;
otherwise, there must be a solution N <= K.

Time Complexity:

Time O(K), Space O(1)

    public int smallestRepunitDivByK(int K) {
        if (K % 2 == 0 || K % 5 == 0) return -1;
        int r = 0;
        for (int N = 1; N <= K; ++N) {
            r = (r * 10 + 1) % K;
            if (r == 0) return N;
        }
        return -1;
    }

https://www.acwing.com/solution/LeetCode/content/1249/

给定正整数 K，你需要找出可以被 K 整除的、仅包含数字 1 的最小正整数 N。

返回 N 的长度。如果不存在这样的 N，就返回 -1。

样例

输入：1
输出：1
解释：最小的答案是 N = 1，其长度为 1。

输入：2
输出：-1
解释：不存在可被 2 整除的正整数 N 。

输入：3
输出：3
解释：最小的答案是 N = 111，其长度为 3。




1. 从 1 开始枚举 N 的长度，在枚举过程中，每次添加一个 1 之后，重新计算出当前的余数 c，之后再继续用 c 乘 10 加 1 继续尝试。
2. 如果枚举过程中 c 重复出现，则说明答案不存在。如果 c 为 0，则说明找到了可以被 K 整除的数字。

时间复杂度

• 最多遍历 K 个余数，故最多枚举 K 次就知道答案存在或者不存在，时间复杂度为 $O(K)$。

空间复杂度

• 需要记录余数是否出现过，故空间复杂度为 $O(K)$。