Jobs

Interviews

Discussions

Smallest Integer Divisible by K

Medium

Asked by:

22 views

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 <= 10⁵

Try coding it in LeetCode

Smallest Integer Divisible by K

Medium

Asked by:

22 views

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 <= 10⁵

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values for K? Can K be negative or zero?
If there is no integer of the form 1, 11, 111, ... that is divisible by K, what should the function return?
Are we looking for the smallest *number of digits* (e.g., 111 is smaller than 1111) or the smallest *value* (which would be the same in this problem, but good to clarify for related problems)?
Can K be a very large number, potentially requiring me to be mindful of integer overflow when constructing the multiples of 1?
Is there a theoretical upper bound on the number of digits I need to check before determining that no solution exists?

Brute Force Solution

Approach

The brute force approach means we'll try every possible length, one by one, until we find a number that meets our requirement of being divisible by K. We'll start with the smallest possible length and keep going until we find one that works, or until we decide it's impossible.

Here's how the algorithm would work step-by-step:

Start by checking the number 1. See if it's divisible by K.
If 1 is not divisible by K, then check the number 11 (which is two ones). See if that's divisible by K.
If 11 is not divisible by K, then check the number 111 (which is three ones). See if that's divisible by K.
Keep adding another 1 to the end of the number you're checking, and see if that new number is divisible by K.
If you've tried a really, really long number and still haven't found one that's divisible by K, then you can stop and conclude that there's no solution.

Code Implementation

def smallest_integer_divisible_by_k_brute_force(k):
    length = 1
    number = 1

    while length <= 100000:
        # Check if the current number is divisible by k
        if number % k == 0:
            return length

        # If not, create the next number by appending a 1
        number = (number * 10 + 1) % k

        # This is needed so that the numbers don't get too large
        # and cause issues with Python's integer size limits.

        length += 1

    # If we've tried a lot of numbers and haven't found one,
    # it's very likely that no such number exists.
    return -1

Big(O) Analysis

Time Complexity

O(K) – The algorithm iteratively checks numbers formed by appending '1' until a number divisible by K is found or we've checked K numbers. In the worst case, we iterate up to K times. Inside the loop, the modulo operation (%) takes constant time. Therefore, the time complexity is dominated by the number of iterations, which is at most K.

Space Complexity

O(1) – The provided approach calculates the remainder on each iteration without storing the entire number. It keeps track of a single number which represents the current sequence of ones modulo K. Therefore, the space used is constant and independent of K. We do not use auxiliary data structures like arrays or hash maps. Thus, the space complexity is O(1).

Optimal Solution

Approach

The goal is to find the smallest number made of only 1s that is perfectly divisible by a given number. Instead of checking every number, we use remainders to avoid unnecessary calculations and quickly find the solution, or determine that one doesn't exist.

Here's how the algorithm would work step-by-step:

Start building a number consisting of only 1s, digit by digit.
Keep track of the remainder when this number is divided by the given number.
If the remainder becomes zero, then we've found our answer: the number of 1s is the answer.
If we encounter a remainder that we've seen before, then it means that the pattern will repeat and there's no solution.
If we have a repeating remainder, then there's no number consisting of only 1s that is perfectly divisible by the given number.

Code Implementation

def smallest_integer_divisible_by_k(divisor):
    remainder = 0
    length_of_number = 0
    remainders_seen = set()

    while True:
        length_of_number += 1
        remainder = (remainder * 10 + 1) % divisor

        # If remainder is 0, we found our number.
        if remainder == 0:
            return length_of_number

        # If remainder is repeating, no solution.
        if remainder in remainders_seen:
            return -1

        remainders_seen.add(remainder)

Big(O) Analysis

Time Complexity

O(K) – The algorithm iterates at most K times because the remainder when dividing by K can only take on K distinct values (0 to K-1). If a remainder repeats, it means we've entered a cycle and no solution exists, so the loop terminates. Therefore, the maximum number of iterations is bounded by K, making the time complexity O(K).

Space Complexity

O(K) – The algorithm uses a set (or similar data structure) to store the remainders encountered so far. In the worst-case scenario, before a repeating remainder is found or a remainder of 0 is achieved, the set could potentially store all possible remainders when dividing by K. Therefore, the space used by the set is proportional to K, where K is the input number. This means the auxiliary space complexity is O(K).

Edge Cases

Case	How to Handle
K is zero	Return -1 immediately, as no number is divisible by zero.
K is negative	Take the absolute value of K, since divisibility applies to negative and positive integers.
K is 1	Return 1 immediately, as 1 is divisible by 1.
Integer overflow in the remainder calculation	Use modulo operator (%) at each step to keep the remainder within the integer range.
No solution exists (infinite loop)	Track seen remainders and if a remainder repeats, return -1 because the search will loop indefinitely.
Resulting length exceeds integer limit	Return -1 if the length exceeds a reasonable limit (e.g., 100000) indicating likely infinite loop or impractical result.
K is a large prime number	The loop may run for a significant number of iterations before a multiple is found, so ensure the algorithm is efficient with memoization.
K is a power of 10	The solution should handle this case without any specific optimization, finding the solution as expected.

K is zero

How to Handle:

Return -1 immediately, as no number is divisible by zero.

K is negative

How to Handle:

Take the absolute value of K, since divisibility applies to negative and positive integers.

K is 1

How to Handle:

Return 1 immediately, as 1 is divisible by 1.

Integer overflow in the remainder calculation

How to Handle:

Use modulo operator (%) at each step to keep the remainder within the integer range.

No solution exists (infinite loop)

How to Handle:

Track seen remainders and if a remainder repeats, return -1 because the search will loop indefinitely.

Resulting length exceeds integer limit

How to Handle:

Return -1 if the length exceeds a reasonable limit (e.g., 100000) indicating likely infinite loop or impractical result.

K is a large prime number

How to Handle:

The loop may run for a significant number of iterations before a multiple is found, so ensure the algorithm is efficient with memoization.

K is a power of 10

How to Handle:

The solution should handle this case without any specific optimization, finding the solution as expected.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values for K? Can K be negative or zero?
If there is no integer of the form 1, 11, 111, ... that is divisible by K, what should the function return?
Are we looking for the smallest *number of digits* (e.g., 111 is smaller than 1111) or the smallest *value* (which would be the same in this problem, but good to clarify for related problems)?
Can K be a very large number, potentially requiring me to be mindful of integer overflow when constructing the multiples of 1?
Is there a theoretical upper bound on the number of digits I need to check before determining that no solution exists?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Start by checking the number 1. See if it's divisible by K.
If 1 is not divisible by K, then check the number 11 (which is two ones). See if that's divisible by K.
If 11 is not divisible by K, then check the number 111 (which is three ones). See if that's divisible by K.
Keep adding another 1 to the end of the number you're checking, and see if that new number is divisible by K.
If you've tried a really, really long number and still haven't found one that's divisible by K, then you can stop and conclude that there's no solution.

Code Implementation

def smallest_integer_divisible_by_k_brute_force(k):
    length = 1
    number = 1

    while length <= 100000:
        # Check if the current number is divisible by k
        if number % k == 0:
            return length

        # If not, create the next number by appending a 1
        number = (number * 10 + 1) % k

        # This is needed so that the numbers don't get too large
        # and cause issues with Python's integer size limits.

        length += 1

    # If we've tried a lot of numbers and haven't found one,
    # it's very likely that no such number exists.
    return -1

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Start building a number consisting of only 1s, digit by digit.
Keep track of the remainder when this number is divided by the given number.
If the remainder becomes zero, then we've found our answer: the number of 1s is the answer.
If we encounter a remainder that we've seen before, then it means that the pattern will repeat and there's no solution.
If we have a repeating remainder, then there's no number consisting of only 1s that is perfectly divisible by the given number.

Code Implementation

def smallest_integer_divisible_by_k(divisor):
    remainder = 0
    length_of_number = 0
    remainders_seen = set()

    while True:
        length_of_number += 1
        remainder = (remainder * 10 + 1) % divisor

        # If remainder is 0, we found our number.
        if remainder == 0:
            return length_of_number

        # If remainder is repeating, no solution.
        if remainder in remainders_seen:
            return -1

        remainders_seen.add(remainder)

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
K is zero	Return -1 immediately, as no number is divisible by zero.
K is negative	Take the absolute value of K, since divisibility applies to negative and positive integers.
K is 1	Return 1 immediately, as 1 is divisible by 1.
Integer overflow in the remainder calculation	Use modulo operator (%) at each step to keep the remainder within the integer range.
No solution exists (infinite loop)	Track seen remainders and if a remainder repeats, return -1 because the search will loop indefinitely.
Resulting length exceeds integer limit	Return -1 if the length exceeds a reasonable limit (e.g., 100000) indicating likely infinite loop or impractical result.
K is a large prime number	The loop may run for a significant number of iterations before a multiple is found, so ensure the algorithm is efficient with memoization.
K is a power of 10	The solution should handle this case without any specific optimization, finding the solution as expected.

K is zero

How to Handle:

Return -1 immediately, as no number is divisible by zero.

K is negative

How to Handle:

Take the absolute value of K, since divisibility applies to negative and positive integers.

K is 1

How to Handle:

Return 1 immediately, as 1 is divisible by 1.

Integer overflow in the remainder calculation

How to Handle:

Use modulo operator (%) at each step to keep the remainder within the integer range.

No solution exists (infinite loop)

How to Handle:

Track seen remainders and if a remainder repeats, return -1 because the search will loop indefinitely.

Resulting length exceeds integer limit

How to Handle:

Return -1 if the length exceeds a reasonable limit (e.g., 100000) indicating likely infinite loop or impractical result.

K is a large prime number

How to Handle:

The loop may run for a significant number of iterations before a multiple is found, so ensure the algorithm is efficient with memoization.

K is a power of 10

How to Handle:

The solution should handle this case without any specific optimization, finding the solution as expected.