We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Smallest Number With Given Digit Product

Number: 3111

Difficulty: Medium

Paid? Yes

Companies: Microsoft

Problem Description

Given a positive integer n, find the smallest positive integer (represented as a string) such that the product of its digits equals n. If no such number exists, return "-1".

Key Insights

  • For numbers less than 10, the answer is simply the number itself.
  • Factorize n by attempting to divide by digits from 9 down to 2. This is because digits closer to 9 will provide the least number of factors, but later the sorted order will yield the smallest possible number.
  • If after factorization n is not reduced to 1, it means n has a prime factor greater than 9 and no valid factorization exists.
  • Sorting the collected factors in increasing order will construct the smallest possible number.

Space and Time Complexity

Time Complexity: O(log n) in most cases, because n is divided repeatedly by factors between 2 and 9. Space Complexity: O(1), as only a constant amount of extra space is used aside from the output.

Solution

The solution employs a greedy strategy by trying to factorize the given number using digits 9 to 2. Each time a digit divides the number exactly, we record that digit and update the number. After factorization, if the number is not 1, a valid factorization is not possible, so we return "-1". Otherwise, we sort the list of factors in ascending order to form the smallest integer. This approach leverages simple arithmetic operations and sorting a small list of factors, making it efficient given the constraints.

Code Solutions

def smallestNumber(n: int) -> str:
    # If n is a single digit, it's already the answer.
    if n < 10:
        return str(n)
    
    digits = []  # To store factors corresponding to digits.
    
    # Try to factorize n using digits from 9 to 2.
    for d in range(9, 1, -1):
        while n % d == 0:
            digits.append(d)  # Record the digit
            n //= d  # Reduce n by factor d
    
    # If not completely factorized, product cannot be represented.
    if n != 1:
        return "-1"
    
    # Sort digits to form the smallest possible number.
    digits.sort()
    return "".join(str(d) for d in digits)

# Example usage:
print(smallestNumber(105))  # Expected Output: "357"
print(smallestNumber(7))    # Expected Output: "7"
print(smallestNumber(44))   # Expected Output: "-1"
← Back to All Questions