Jobs

Interviews

Discussions

Smallest Number With Given Digit Product

Medium

Asked by:

33 views

Topics:

Greedy AlgorithmsArrays

Given a positive integer product, find the smallest positive integer that has a digit product equal to product.

If there is no such integer, return -1.

Example 1:

Input: product = 12
Output: 26

Example 2:

Input: product = 19
Output: -1

Example 3:

Input: product = 1
Output: 1

Constraints:

1 <= product <= 10⁹

Try coding it in LeetCode

Smallest Number With Given Digit Product

Medium

Asked by:

33 views

Topics:

Greedy AlgorithmsArrays

Given a positive integer product, find the smallest positive integer that has a digit product equal to product.

If there is no such integer, return -1.

Example 1:

Input: product = 12
Output: 26

Example 2:

Input: product = 19
Output: -1

Example 3:

Input: product = 1
Output: 1

Constraints:

1 <= product <= 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 possible range of values for the input product?
If there is no integer whose digits multiply to the product, should I return -1 as an integer or a string?
If multiple smallest numbers exist with the same digit product, is there any preference for which one to return, or can I return any of them?
Is the input product guaranteed to be a positive integer?
Can the product be 0 or 1, and if so, how should those cases be handled?

Brute Force Solution

Approach

The brute force method involves checking every possible number to see if its digits multiply to the target product. We keep generating numbers, calculating their digit product, and seeing if it matches the required product. We continue until we find the smallest such number.

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

Start checking numbers from the smallest positive integer, which is 1.
For each number, multiply its digits together.
Compare the result of the multiplication with the target product.
If the multiplied digits equal the target product, we have found a potential solution. Save this number.
If the multiplied digits are not equal to the target product, discard the number and continue to the next number.
Continue checking numbers and saving any number whose digits multiply to the target product.
Once a potential solution has been found, we need to verify that it is actually the smallest number to do so. Continue to check the remaining numbers and if a smaller solution is found, replace the previous solution with this one. This guarantees that at the end of the process, we have the smallest number.
If we have checked every possible number up to a reasonable limit (since the product could also not be possible), and haven't found any number, it means there isn't a solution within that limit.

Code Implementation

def smallest_number_with_product_brute_force(target_product):
    current_number = 1

    while True:
        product_of_digits = 1
        temp_number = current_number

        while temp_number > 0:
            digit = temp_number % 10
            product_of_digits *= digit
            temp_number //= 10

        # Check if the product matches the target.
        if product_of_digits == target_product:

            # Found the smallest number.
            return current_number

        current_number += 1

def smallest_number_with_given_digit_product(target_product):
    if target_product == 0:
        return 10

    if target_product == 1:
        return 1

    # Utilize brute force implementation to find the number
    result = smallest_number_with_product_brute_force(target_product)
    return result

Big(O) Analysis

Time Complexity

O(10^n) – The described brute-force approach iterates through numbers starting from 1 until a solution is found or a reasonable limit is reached. The 'input size' in this case can be conceptualized as the number of digits 'n' in the potential solution number. However, the algorithm essentially tries every number with up to 'n' digits. The number of integers to check grows exponentially as the number of digits increases. In the worst case, to find a solution with 'n' digits, or determine no such solution exists, the algorithm could potentially check all numbers up to 10^n. Therefore, the time complexity is O(10^n), where n represents the number of digits in the smallest possible number with the given product or the maximum number of digits we consider before concluding no solution exists.

Space Complexity

O(1) – The algorithm, as described, iteratively checks numbers and their digit products. It stores at most one potential solution (the smallest number found so far) and the current number being checked. These variables require constant space, independent of the target product, N. Therefore, the auxiliary space complexity is O(1).

Optimal Solution

Approach

The problem asks us to find the smallest number whose digits, when multiplied together, equal a given product. The key is to build the number from its digits starting from the ones place and working our way up, prioritizing larger digits to minimize the overall number of digits and ensure a smaller result.

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

If the product is 0, the answer is simply 10, since any number multiplied by 0 is 0. If the product is 1, the smallest number is 1.
Start with the largest single-digit numbers (9, 8, 7, and so on down to 2) and see if they divide evenly into the product.
If a digit divides evenly into the product, that digit becomes part of our number. Divide the product by this digit to update the remaining product.
Repeat this process of checking divisibility, starting with the largest digits and working downwards, until the remaining product is 1. This means we've found all the digits.
If at any point the remaining product is not 1 and no digit between 2 and 9 can divide evenly into it, then there is no solution. Return an indicator showing there is no solution.
Once we've found all the digits, arrange them in increasing order to create the smallest possible number. This puts the smallest digits in the higher place values, resulting in the smallest overall number.

Code Implementation

def find_smallest_number_with_product(product):
    if product == 0:
        return 10
    if product == 1:
        return 1

    digit_factors = []
    # Iterate through digits 9 to 2 to find factors.
    for digit in range(9, 1, -1):
        while product % digit == 0:
            product //= digit
            digit_factors.append(digit)

    # If product is not 1, no solution exists
    if product != 1:
        return -1

    digit_factors.sort()
    # Construct smallest number from sorted digits.
    result = 0
    for digit in digit_factors:
        result = result * 10 + digit

    return result

Big(O) Analysis

Time Complexity

O(log n) – The algorithm iteratively divides the input product n by digits from 9 down to 2. In the worst-case scenario, n is a product of many small prime factors, such as 2 or 3. The number of divisions is bounded by the number of digits in the final result. Since we are repeatedly reducing n by factors between 2 and 9, the number of iterations (and therefore the number of digits) is logarithmic with respect to n. Therefore, the time complexity is O(log n).

Space Complexity

O(log N) – The algorithm stores the digits of the result in a data structure (implicitly a list or string builder). The number of digits needed to represent the smallest number with a given product 'N' is at most log_2(N) (worst case if we repeatedly divide by 2). Sorting these digits requires additional space proportional to the number of digits. Therefore, the auxiliary space used is proportional to the number of digits, which is O(log N) in the worst case, where N is the input product.

Edge Cases

Case	How to Handle
Product is 0	Return 10 as the smallest positive integer whose digits multiply to 0 is 10.
Product is 1	Return 1, because 1 is the smallest positive integer whose digits multiply to 1.
Product is a prime number greater than 9	Return -1 because no combination of single digits can multiply to a prime number greater than 9.
Product is a very large number that might result in integer overflow when constructing the final number	The algorithm should avoid directly constructing the final number as an integer until the digits are determined to avoid potential overflow; instead, store digits in a list or string then sort and convert if needed.
Product is a number with only one factor > 9, which makes a combination of single-digit factors impossible	Return -1 if after repeated division by factors 9 to 2, the remaining product is still > 9.
Product is a perfect square like 4,9,16,25,36,49,64,81	Handle these cases appropriately by repeatedly dividing until only single digit factors remain.
Product contains only 2's and 3's as factors (e.g., 223*3).	The algorithm should ensure that the digits are arranged in ascending order for the smallest possible number.
Product is a negative number	Return -1 because the problem statement asks for a positive integer product.

Product is 0

How to Handle:

Return 10 as the smallest positive integer whose digits multiply to 0 is 10.

Product is 1

How to Handle:

Return 1, because 1 is the smallest positive integer whose digits multiply to 1.

Product is a prime number greater than 9

How to Handle:

Return -1 because no combination of single digits can multiply to a prime number greater than 9.

Product is a very large number that might result in integer overflow when constructing the final number

How to Handle:

The algorithm should avoid directly constructing the final number as an integer until the digits are determined to avoid potential overflow; instead, store digits in a list or string then sort and convert if needed.

Product is a number with only one factor > 9, which makes a combination of single-digit factors impossible

How to Handle:

Return -1 if after repeated division by factors 9 to 2, the remaining product is still > 9.

Product is a perfect square like 4,9,16,25,36,49,64,81

How to Handle:

Handle these cases appropriately by repeatedly dividing until only single digit factors remain.

Product contains only 2's and 3's as factors (e.g., 2*2*3*3).

How to Handle:

The algorithm should ensure that the digits are arranged in ascending order for the smallest possible number.

Product is a negative number

How to Handle:

Return -1 because the problem statement asks for a positive integer product.

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 possible range of values for the input product?
If there is no integer whose digits multiply to the product, should I return -1 as an integer or a string?
If multiple smallest numbers exist with the same digit product, is there any preference for which one to return, or can I return any of them?
Is the input product guaranteed to be a positive integer?
Can the product be 0 or 1, and if so, how should those cases be handled?

Brute Force Solution

Approach

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

Start checking numbers from the smallest positive integer, which is 1.
For each number, multiply its digits together.
Compare the result of the multiplication with the target product.
If the multiplied digits equal the target product, we have found a potential solution. Save this number.
If the multiplied digits are not equal to the target product, discard the number and continue to the next number.
Continue checking numbers and saving any number whose digits multiply to the target product.
Once a potential solution has been found, we need to verify that it is actually the smallest number to do so. Continue to check the remaining numbers and if a smaller solution is found, replace the previous solution with this one. This guarantees that at the end of the process, we have the smallest number.
If we have checked every possible number up to a reasonable limit (since the product could also not be possible), and haven't found any number, it means there isn't a solution within that limit.

Code Implementation

def smallest_number_with_product_brute_force(target_product):
    current_number = 1

    while True:
        product_of_digits = 1
        temp_number = current_number

        while temp_number > 0:
            digit = temp_number % 10
            product_of_digits *= digit
            temp_number //= 10

        # Check if the product matches the target.
        if product_of_digits == target_product:

            # Found the smallest number.
            return current_number

        current_number += 1

def smallest_number_with_given_digit_product(target_product):
    if target_product == 0:
        return 10

    if target_product == 1:
        return 1

    # Utilize brute force implementation to find the number
    result = smallest_number_with_product_brute_force(target_product)
    return result

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

If the product is 0, the answer is simply 10, since any number multiplied by 0 is 0. If the product is 1, the smallest number is 1.
Start with the largest single-digit numbers (9, 8, 7, and so on down to 2) and see if they divide evenly into the product.
If a digit divides evenly into the product, that digit becomes part of our number. Divide the product by this digit to update the remaining product.
Repeat this process of checking divisibility, starting with the largest digits and working downwards, until the remaining product is 1. This means we've found all the digits.
If at any point the remaining product is not 1 and no digit between 2 and 9 can divide evenly into it, then there is no solution. Return an indicator showing there is no solution.
Once we've found all the digits, arrange them in increasing order to create the smallest possible number. This puts the smallest digits in the higher place values, resulting in the smallest overall number.

Code Implementation

def find_smallest_number_with_product(product):
    if product == 0:
        return 10
    if product == 1:
        return 1

    digit_factors = []
    # Iterate through digits 9 to 2 to find factors.
    for digit in range(9, 1, -1):
        while product % digit == 0:
            product //= digit
            digit_factors.append(digit)

    # If product is not 1, no solution exists
    if product != 1:
        return -1

    digit_factors.sort()
    # Construct smallest number from sorted digits.
    result = 0
    for digit in digit_factors:
        result = result * 10 + digit

    return result

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Product is 0	Return 10 as the smallest positive integer whose digits multiply to 0 is 10.
Product is 1	Return 1, because 1 is the smallest positive integer whose digits multiply to 1.
Product is a prime number greater than 9	Return -1 because no combination of single digits can multiply to a prime number greater than 9.
Product is a very large number that might result in integer overflow when constructing the final number	The algorithm should avoid directly constructing the final number as an integer until the digits are determined to avoid potential overflow; instead, store digits in a list or string then sort and convert if needed.
Product is a number with only one factor > 9, which makes a combination of single-digit factors impossible	Return -1 if after repeated division by factors 9 to 2, the remaining product is still > 9.
Product is a perfect square like 4,9,16,25,36,49,64,81	Handle these cases appropriately by repeatedly dividing until only single digit factors remain.
Product contains only 2's and 3's as factors (e.g., 223*3).	The algorithm should ensure that the digits are arranged in ascending order for the smallest possible number.
Product is a negative number	Return -1 because the problem statement asks for a positive integer product.

Product is 0

How to Handle:

Return 10 as the smallest positive integer whose digits multiply to 0 is 10.

Product is 1

How to Handle:

Return 1, because 1 is the smallest positive integer whose digits multiply to 1.

Product is a prime number greater than 9

How to Handle:

Return -1 because no combination of single digits can multiply to a prime number greater than 9.

Product is a very large number that might result in integer overflow when constructing the final number

How to Handle:

Product is a number with only one factor > 9, which makes a combination of single-digit factors impossible

How to Handle:

Return -1 if after repeated division by factors 9 to 2, the remaining product is still > 9.

Product is a perfect square like 4,9,16,25,36,49,64,81

How to Handle:

Handle these cases appropriately by repeatedly dividing until only single digit factors remain.

Product contains only 2's and 3's as factors (e.g., 2*2*3*3).

How to Handle:

The algorithm should ensure that the digits are arranged in ascending order for the smallest possible number.

Product is a negative number

How to Handle:

Return -1 because the problem statement asks for a positive integer product.