Jobs

Interviews

Discussions

Smallest Greater Multiple Made of Two Digits

Medium

PayPal

1 view

Topics:

ArraysGreedy Algorithms

Given two positive integers num and k, find the smallest integer greater than or equal to k whose digits are only num or 0. Return -1 if the integer does not exist.

Note:

It is guaranteed that the number of digits in the integer k is less than or equal to 9.
num is an integer between 1 and 9 (inclusive).

Example 1:

Input: num = 6, k = 20
Output: 60
Explanation: 60 is the smallest integer greater than or equal to 20 whose digits are either 6 or 0.

Example 2:

Input: num = 3, k = 5
Output: 30

Example 3:

Input: num = 4, k = 4444
Output: 4444

Example 4:

Input: num = 9, k = 500
Output: 900

Example 5:

Input: num = 1, k = 12
Output: -1

Constraints:

1 <= num <= 9
1 <= k <= 10⁹

Smallest Greater Multiple Made of Two Digits

Medium

PayPal

1 view

Topics:

ArraysGreedy Algorithms

Given two positive integers num and k, find the smallest integer greater than or equal to k whose digits are only num or 0. Return -1 if the integer does not exist.

Note:

It is guaranteed that the number of digits in the integer k is less than or equal to 9.
num is an integer between 1 and 9 (inclusive).

Example 1:

Input: num = 6, k = 20
Output: 60
Explanation: 60 is the smallest integer greater than or equal to 20 whose digits are either 6 or 0.

Example 2:

Input: num = 3, k = 5
Output: 30

Example 3:

Input: num = 4, k = 4444
Output: 4444

Example 4:

Input: num = 9, k = 500
Output: 900

Example 5:

Input: num = 1, k = 12
Output: -1

Constraints:

1 <= num <= 9
1 <= k <= 10⁹

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 are the allowed ranges for digit1, digit2, and n? Can digit1 or digit2 be zero?
If no integer greater than n can be formed using only digit1 and digit2, what should the function return?
Can digit1 and digit2 be the same value? How should this affect the comparison to 'n'?
Is 'n' guaranteed to be a positive integer, or can it be zero or negative?
Should I consider the most significant digit of the generated number to be non-zero (i.e., no leading zeros)? If digit1 or digit2 is zero, is forming a number like '05' allowed?

Brute Force Solution

Approach

The brute force approach to this problem is like trying every possible number made from the two given digits, until we find one that is a multiple of the target number. We start small and gradually increase the size of the number, checking each one along the way.

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

Start with the smallest possible numbers you can make using the two allowed digits. For example, if the digits are 1 and 2, begin with 1, 2, 11, 12, 21, 22.
For each of these numbers, check if it's divisible by the target number. To check this, divide the number by the target number and see if the remainder is zero.
If you find a number that is divisible by the target number, stop! That's your answer – the smallest multiple made from those digits.
If you don't find a multiple in the first set of small numbers, make larger numbers using the allowed digits. For example, 111, 112, 121, 122, 211, 212, 221, 222 and so on.
Keep checking each of these larger numbers to see if it is divisible by the target number. Continue making and checking larger and larger numbers until you find a multiple.
Once you find a number that is divisible by the target, that is the smallest multiple you can make from those two digits. You can then stop looking.

Code Implementation

def find_smallest_multiple(divisor, digit1, digit2):
    queue = [digit1, digit2]

    while queue:
        current_number = queue.pop(0)

        # Check if the current number is a multiple of the divisor.
        if current_number % divisor == 0:
            return current_number

        # To avoid infinite loop, check current number is within limits
        if current_number > 10000:
            return -1

        new_number1 = current_number * 10 + digit1

        # Create the next possible number by appending the digits to the queue.
        queue.append(new_number1)

        new_number2 = current_number * 10 + digit2

        queue.append(new_number2)

    return -1

Big(O) Analysis

Time Complexity

O(infinity) – The provided brute force approach generates numbers of increasing length from the two given digits and checks for divisibility by the target number. In the worst case, if no such multiple exists, the algorithm will continue generating and checking larger and larger numbers indefinitely, never terminating. Therefore, the time complexity is effectively infinite because there's no guarantee of finding a solution or a defined limit to the search space.

Space Complexity

O(B) – The space complexity depends on the breadth of the search, as we are effectively performing a breadth-first search of all possible numbers constructible from the two digits. In the worst-case scenario, we may need to explore a very large number of combinations before finding the smallest multiple. B represents the maximum number of intermediate number combinations kept in memory at any point in time; this is driven by the number of combinations created until a suitable multiple is found. Because the problem statement doesn't provide any bound or limit on the size of such combinations, space used will be proportional to maximum numbers generated until the result is found. Therefore, the auxiliary space complexity is O(B).

Optimal Solution

Approach

The key is to generate potential multiples in increasing order and stop as soon as we find one. We can generate these multiples using a breadth-first search approach, prioritizing shorter numbers and avoiding duplicates to improve efficiency.

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

Start with the two allowed digits as the initial possible multiples.
Check if either of these initial numbers is a multiple of the given number. If so, we're done!
If not, create new potential multiples by appending each allowed digit to the existing ones.
Repeat the process of checking if any of the new multiples are divisible and then creating further multiples, but keep track of which numbers we've already checked to avoid doing extra work.
By expanding the possible multiples in this organized way, we are guaranteed to find the smallest one first, if it exists.

Code Implementation

def find_smallest_multiple(divisor, digit_one, digit_two):    queue = [digit_one]
    visited = {digit_one}
    while queue:
        current_number = queue.pop(0)
        # Found the smallest multiple, so return it.
        if current_number % divisor == 0:
            return current_number

        next_number_one = current_number * 10 + digit_one
        if next_number_one <= 100000 and next_number_one not in visited:
            queue.append(next_number_one)
            visited.add(next_number_one)

        next_number_two = current_number * 10 + digit_two
        # Prevent very large numbers and avoid revisiting.
        if next_number_two <= 100000 and next_number_two not in visited:
            queue.append(next_number_two)
            visited.add(next_number_two)

    return -1

Big(O) Analysis

Time Complexity

O(2^k) – The time complexity is determined by the breadth-first search generating multiples. In the worst-case, we might need to explore all possible numbers made of the two given digits up to a certain length 'k', where 'k' represents the number of digits in the smallest multiple. Because each digit can be one of two choices, the number of possible multiples grows exponentially. Therefore, we could generate up to 2^k potential multiples, where 'k' is the number of digits in the desired result. Each multiple requires a division check, which can be considered O(1). Thus, the overall time complexity is O(2^k).

Space Complexity

O(N) – The breadth-first search uses a queue to store potential multiples. In the worst case, before finding a multiple of the input number, the queue might contain all possible multiples of increasing length, made from the two allowed digits, up to a certain number of digits. The number of digits needed depends on the magnitude of the input number. Therefore, the auxiliary space required to store the queue of potential multiples can grow linearly with the magnitude of the smallest multiple, N, that is divisible by the input number, where N is the value of the smallest multiple and not the input number itself. We also use a set to store the visited numbers, which can also grow up to size N in the worst case. Thus the overall space complexity is O(N).

Edge Cases

Case	How to Handle
digit1 or digit2 are invalid (e.g., not digits, or outside the 0-9 range).	Validate the inputs digit1 and digit2, and throw an exception or return an error code if they are invalid.
n is negative.	Treat n as its absolute value or throw an exception as the problem statement specifies n is a positive integer.
digit1 and digit2 are the same.	The solution should still generate valid numbers composed only of that digit and handle comparisons correctly.
n is very large, causing potential integer overflow when generating numbers.	Use a data type capable of handling larger numbers (e.g., long, BigInteger) or consider a string-based comparison for larger numbers.
No number greater than n can be formed using digit1 and digit2 within a reasonable limit (e.g., maximum number of digits to generate).	Implement a limit on the number of digits or the number of generated numbers, and return a specific value (e.g., -1, null) to indicate no solution found within the limit.
digit1 and digit2 are both zero.	Handle the zero case carefully; the algorithm should generate a number greater than n, and not return zero if n is greater than zero.
n is a very long number composed entirely of the smaller of the two digits (e.g., n=11111, digit1=1, digit2=2).	The algorithm must efficiently generate and compare numbers without unnecessary recursion or string manipulation overhead.
leading zeros in the generated number when one or both digits are 0	Ensure that numbers like '01', '001', etc. are not added if they do not exceed n or are immediately discarded, and instead prioritize other combinations

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 are the allowed ranges for digit1, digit2, and n? Can digit1 or digit2 be zero?
If no integer greater than n can be formed using only digit1 and digit2, what should the function return?
Can digit1 and digit2 be the same value? How should this affect the comparison to 'n'?
Is 'n' guaranteed to be a positive integer, or can it be zero or negative?
Should I consider the most significant digit of the generated number to be non-zero (i.e., no leading zeros)? If digit1 or digit2 is zero, is forming a number like '05' allowed?

Brute Force Solution

Approach

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

Start with the smallest possible numbers you can make using the two allowed digits. For example, if the digits are 1 and 2, begin with 1, 2, 11, 12, 21, 22.
For each of these numbers, check if it's divisible by the target number. To check this, divide the number by the target number and see if the remainder is zero.
If you find a number that is divisible by the target number, stop! That's your answer – the smallest multiple made from those digits.
If you don't find a multiple in the first set of small numbers, make larger numbers using the allowed digits. For example, 111, 112, 121, 122, 211, 212, 221, 222 and so on.
Keep checking each of these larger numbers to see if it is divisible by the target number. Continue making and checking larger and larger numbers until you find a multiple.
Once you find a number that is divisible by the target, that is the smallest multiple you can make from those two digits. You can then stop looking.

Code Implementation

def find_smallest_multiple(divisor, digit1, digit2):
    queue = [digit1, digit2]

    while queue:
        current_number = queue.pop(0)

        # Check if the current number is a multiple of the divisor.
        if current_number % divisor == 0:
            return current_number

        # To avoid infinite loop, check current number is within limits
        if current_number > 10000:
            return -1

        new_number1 = current_number * 10 + digit1

        # Create the next possible number by appending the digits to the queue.
        queue.append(new_number1)

        new_number2 = current_number * 10 + digit2

        queue.append(new_number2)

    return -1

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

Start with the two allowed digits as the initial possible multiples.
Check if either of these initial numbers is a multiple of the given number. If so, we're done!
If not, create new potential multiples by appending each allowed digit to the existing ones.
Repeat the process of checking if any of the new multiples are divisible and then creating further multiples, but keep track of which numbers we've already checked to avoid doing extra work.
By expanding the possible multiples in this organized way, we are guaranteed to find the smallest one first, if it exists.

Code Implementation

def find_smallest_multiple(divisor, digit_one, digit_two):    queue = [digit_one]
    visited = {digit_one}
    while queue:
        current_number = queue.pop(0)
        # Found the smallest multiple, so return it.
        if current_number % divisor == 0:
            return current_number

        next_number_one = current_number * 10 + digit_one
        if next_number_one <= 100000 and next_number_one not in visited:
            queue.append(next_number_one)
            visited.add(next_number_one)

        next_number_two = current_number * 10 + digit_two
        # Prevent very large numbers and avoid revisiting.
        if next_number_two <= 100000 and next_number_two not in visited:
            queue.append(next_number_two)
            visited.add(next_number_two)

    return -1

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
digit1 or digit2 are invalid (e.g., not digits, or outside the 0-9 range).	Validate the inputs digit1 and digit2, and throw an exception or return an error code if they are invalid.
n is negative.	Treat n as its absolute value or throw an exception as the problem statement specifies n is a positive integer.
digit1 and digit2 are the same.	The solution should still generate valid numbers composed only of that digit and handle comparisons correctly.
n is very large, causing potential integer overflow when generating numbers.	Use a data type capable of handling larger numbers (e.g., long, BigInteger) or consider a string-based comparison for larger numbers.
No number greater than n can be formed using digit1 and digit2 within a reasonable limit (e.g., maximum number of digits to generate).	Implement a limit on the number of digits or the number of generated numbers, and return a specific value (e.g., -1, null) to indicate no solution found within the limit.
digit1 and digit2 are both zero.	Handle the zero case carefully; the algorithm should generate a number greater than n, and not return zero if n is greater than zero.
n is a very long number composed entirely of the smaller of the two digits (e.g., n=11111, digit1=1, digit2=2).	The algorithm must efficiently generate and compare numbers without unnecessary recursion or string manipulation overhead.
leading zeros in the generated number when one or both digits are 0	Ensure that numbers like '01', '001', etc. are not added if they do not exceed n or are immediately discarded, and instead prioritize other combinations