1015. Smallest Integer Divisible by K¶
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 <= 105
Analysis¶
By observation, we can find that the only case that will return -1 is when there is a repetend for the reminder as we grow our candidate number, so we can just create a set that will store all the prevous reminders and see if current reminder already exist or not. However, if we just arbitarily increase our candidate number, it will result in overflow, so we need to apply the modulus trick:
r = n % k
n = m * k + r
10 * n + 1 = 10 * (m * k + r) + 1
10 * n + 1 = 10 * m * k + 10 * r + 1
(10 * n + 1) % k = (10 * m * k + 10 * r + 1) % k
(10 * n + 1) % k = (10 * r + 1) % k // (10 * m * k) % k = 0
so whatever n is, (10 * n + 1) % k equals to (10 * r + 1) % k, where r is n % k. So that's why we only need to keep the remainder.
Or inituitively, we can see that reminder is always in the range from 0 to K. No mater how do we increase our number, we just need to keep the reminder (% K result), since we are only interested in the reminder of the long number.
So we conclude that r = (r * 10 + 1) % K, where left-side r is our new r.
However, there is a even smarter way to reduce the space:
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.
This will allow us to just check these two simple cases to determine if we should return -1.
Time: O(K)
Code: with extra space¶
class Solution {
public:
int smallestRepunitDivByK(int K) {
set<int> vis;
int curr = 0, cnt = 0;
while (1) {
curr = (curr * 10 + 1) % K;
cnt ++;
int mod = curr % K;
if (vis.count(mod)) return -1;
else if (mod == 0) return cnt;
else vis.insert(mod);
}
return cnt;
}
};
Space: O(K)
Code: use math¶
int smallestRepunitDivByK(int K) {
for (int r = 0, N = 1; N <= K; ++N)
if ((r = (r * 10 + 1) % K) == 0)
return N;
return -1;
}
Space: O(1)