Skip to content

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 remainder as we grow our candidate number, so we can just create a set that will store all the previous remainders and see if the current remainder already exists or not. However, if we just arbitrarily 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 intuitively, we can see that the remainder is always in the range from 0 to K. No matter how we increase our number, we just need to keep the remainder (% K result), since we are only interested in the remainder of the long number.

So we conclude that r = (r * 10 + 1) % K, where left-side r is our new r.

However, there is an 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 pigeonhole problem:
There must be at least two identical 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

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

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)