Leetcode 1015: Smallest Integer Divisible by K

Input: The input consists of a single integer k, where k is a positive integer.

Example: k = 7

Constraints:

• 1 <= k <= 10^5

Output: The output should be an integer representing the length of the smallest integer n that is divisible by k and only contains the digit 1, or -1 if no such integer exists.

Example: Output: 6

Constraints:

• The result must be an integer.

Goal: To determine the length of the smallest integer n that is divisible by k and consists only of the digit 1.

Steps:

• Iterate through possible lengths of numbers formed only by the digit 1.

• For each length, compute the number formed by that many 1s, and check if it's divisible by k.

• Return the length of the first such number, or -1 if no such number exists.

Goal: The solution needs to handle large values of k efficiently.

Steps:

• The value of k can be as large as 100,000, requiring an efficient solution to avoid brute force checks for large numbers.

Assumptions:

• There is always a valid input integer k, and it will be between 1 and 100,000.

• Input: Input: k = 1

• Explanation: The smallest number divisible by 1 is simply 1, which has length 1.

• Input: Input: k = 2

• Explanation: There is no number formed by 1s that is divisible by 2, so the output is -1.

• Input: Input: k = 3

• Explanation: The smallest number divisible by 3 is 111, which has length 3.

Approach: The approach is to iteratively compute the remainder when numbers formed by the digit 1 are divided by k, and check when this remainder becomes zero. The first such number will give us the length of the desired number.

Observations:

• We can form numbers using the digit 1 repeatedly, and compute their remainder with respect to k.

• If the remainder becomes zero, we've found the smallest such number.

• Rather than directly constructing the large number, we can calculate the remainder iteratively by considering the number as a series of digits (all 1s).

Steps:

• 1. Start with a remainder of 0 and a number with the digit 1.

• 2. For each subsequent digit, update the remainder using the formula: remainder = (remainder * 10 + 1) % k.

• 3. Check if the remainder is 0. If it is, return the length of the number formed.

• 4. If no such number is found, return -1.

Empty Inputs:

• The input is guaranteed to be a positive integer k, so no need to handle empty inputs.

Large Inputs:

• For large values of k, the solution should handle remainders efficiently without constructing large numbers.

Special Values:

• When k is 1, the smallest number is 1 itself, which has length 1.

Constraints:

• Ensure that the solution works efficiently for large k values up to 100,000.

int smallestRepunitDivByK(int k) {
    for(int r = 0, N = 1; N <= k; N++)
    if((r = (r * 10 + 1)%k )== 0) return N;
    return -1;
}

1 : Function Declaration

int smallestRepunitDivByK(int k) {

Declares the function `smallestRepunitDivByK`, which takes an integer `k` and returns the smallest integer `N` such that the number formed by repeating '1' `N` times is divisible by `k`.

2 : Loop Initialization

    for(int r = 0, N = 1; N <= k; N++)

Initializes a loop with two variables: `r`, which will store the remainder when dividing the current number by `k`, and `N`, which represents the number of '1's in the current candidate number. The loop continues until `N` exceeds `k`.

3 : Modular Arithmetic

    if((r = (r * 10 + 1)%k )== 0) return N;

For each iteration, the number formed by repeating '1' is calculated modulo `k` using the formula `(r * 10 + 1) % k`. If the remainder `r` is zero, it means the number formed by repeating '1' `N` times is divisible by `k`, and the function returns `N`.

4 : Return -1

    return -1;

If no such `N` is found after looping through all possible values up to `k`, the function returns `-1`, indicating no solution exists.

Best Case: O(k)

Average Case: O(k)

Worst Case: O(k)

Description: The solution iterates through the remainders for at most k iterations, leading to a time complexity of O(k).

Best Case: O(1)

Worst Case: O(1)

Description: The space complexity is O(1) as we only maintain a few variables to track the remainder and length of the number.

Leetcode 1015: Smallest Integer Divisible by K

Explore →