Smallest Integer Divisible by K

Problem Statement

In this problem, you are tasked with finding the smallest integer n that is both divisible by a given positive integer k and comprises entirely of the digit 1. The output should be the length of this number n. If such a number does not exist, return -1. The number n can be extremely large, potentially exceeding the capacity of standard 64-bit integers.

Examples

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

Approach and Intuition

The challenge lies in finding a number that meets both a divisibility condition and a numeric composition constraint. We need a method to discover n, where n is the smallest number consisting only of the digit 1 and is also divisible by k.

Several observations and strategies help approach this problem:

1. Begin by creating numbers composed only of the digit 1 in increasing length until you find one that is divisible by k.

2. Utilize modular arithmetic to manage large numbers. Instead of constructing the actual number n, maintain the remainder of n divided by k.

3. Initialize a variable num to represent n being built digit by digit, and a variable remainder to store num % k.

4. Iterate, appending the digit '1' at each step, updating num and remainder. Convert this logic:

   • num = num * 10 + 1
   • remainder = (remainder * 10 + 1) % k This avoids direct computation on potentially monstrous numbers while maintaining accuracy in divisibility checks.

5. If at any step, remainder becomes 0, the current length of num is the answer.

6. If you detect cycles in remainders without hitting zero (suggesting you'll start repeating remainders without finding a zero), the process needs to be aborted and return -1.

7. Since num is only formed of '1's, its length at any time is the count of iterations.

Limitations and Edge Management:

• The obvious edge case is k == 1, which immediately returns 1 since n = 1 is divisible by 1.
• For k = 2 or other even numbers, the divisibility by 1's number is impossible. But the modular approach manages this by cycling through remainders without finding a zero.
• Ensure that the loop only continues safely while maintaining computation efficiency; hence, a fail-safe needs to exist if it can be determined no valid n can be formed (e.g., encountering a repeated remainder before finding a zero).

With the given constraints of k being quite large (up to 105), the method needs to efficiently handle multiple queries without excessive computation delay. The modular approach reduces the potential number size we handle directly and the loop ensures we find an answer without unnecessary calculations.

Solutions

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

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