Code Implementation

class Solution:
    def smallestRepunitDivByK(self, K: int) -> int:
        remainder = 0
        for length in range(1, K + 1):
            remainder = (remainder * 10 + 1) % K
            if remainder == 0:
                return length
        return -1
      

class Solution {
public:
    int smallestRepunitDivByK(int K) {
        int remainder = 0;
        for (int length = 1; length <= K; ++length) {
            remainder = (remainder * 10 + 1) % K;
            if (remainder == 0) return length;
        }
        return -1;
    }
};
      

class Solution {
    public int smallestRepunitDivByK(int K) {
        int remainder = 0;
        for (int length = 1; length <= K; ++length) {
            remainder = (remainder * 10 + 1) % K;
            if (remainder == 0) return length;
        }
        return -1;
    }
}
      

var smallestRepunitDivByK = function(K) {
    let remainder = 0;
    for (let length = 1; length <= K; ++length) {
        remainder = (remainder * 10 + 1) % K;
        if (remainder === 0) return length;
    }
    return -1;
};
      

Problem Description

Given a positive integer K, you are asked to find the length of the smallest positive integer N such that:

• N is composed only of the digit 1 (i.e., N = 1, 11, 111, 1111, ...).
• N is divisible by K (i.e., N % K == 0).

• 1 <= K <= 10^5

• There is at most one valid answer for each K.
• You do not need to construct the actual number N; only its length is required.

Thought Process

At first glance, the problem seems to suggest that we should generate numbers like 1, 11, 111, 1111, and so on, until we find one divisible by K. However, constructing such numbers quickly becomes infeasible, since even for moderate K the integers would have hundreds or thousands of digits.

The key insight is that we do not need to actually build these huge numbers. Instead, we can use modular arithmetic to keep track of the remainder as we append more 1s to our number.

We also realize that if we ever see the same remainder twice while building up our number, we are in a cycle and will never reach a remainder of 0. This is because, with each new digit, the remainder can only take on K possible values (from 0 to K-1), so if we try K times and never find a remainder of 0, it will never happen.

Solution Approach

To solve this problem efficiently, we use the following approach:

1. Check divisibility by 2 or 5: If K is divisible by 2 or 5, there can never be a number made only of 1s that is divisible by K (since such numbers are always odd and do not end in 0 or 5).
2. Use modular arithmetic: Instead of constructing the number, we keep track of the remainder when dividing by K as we "add" each new digit 1 to the right.
   • For example, if the current remainder is r, then the next number (with one more digit 1) will have a remainder of (r * 10 + 1) % K.
3. Iterate up to K times: There are only K possible remainders (from 0 to K-1). If we do not find a remainder of 0 after K steps, we return -1.
4. Return the length: The first time we find a remainder of 0, the current length is our answer.

Example Walkthrough

Let's consider K = 3 as an example:

• Step 1: Start with remainder = 0, length = 1.
• New remainder = (0 * 10 + 1) % 3 = 1 % 3 = 1
• Step 2: length = 2. New remainder = (1 * 10 + 1) % 3 = 11 % 3 = 2
• Step 3: length = 3. New remainder = (2 * 10 + 1) % 3 = 21 % 3 = 0

• Since 2 is divisible by 2, we can immediately return -1, since no number made only of 1s is divisible by 2.

Time and Space Complexity

Brute-force approach: Generating each number with more digits and checking divisibility would require O(N) time and space per step, where N is the number of digits, which can grow extremely large. This is not feasible.

Optimized approach (modular arithmetic):

• Time complexity: O(K) – We perform at most K iterations, each with constant time work.
• Space complexity: O(1) – We only store the current remainder and length; no large numbers or arrays are needed.

Summary

The key to solving the "Smallest Integer Divisible by K" problem efficiently is to avoid constructing large numbers by using modular arithmetic. By updating the remainder as we conceptually append more 1s, we can determine if and when a number of only 1s becomes divisible by K. The solution is both elegant and efficient, requiring only a simple loop and constant space.