Is Smallest Number With Given Digit Product easy or hard?

The problem is typically classified as Medium. The coding portion is short, but recognizing the greedy factorization insight requires understanding how digits represent combinations of prime factors.

Smallest Number With Given Digit Product Python/Java solution

Implement a loop from digit 9 down to 2 and repeatedly divide n when divisible. Append the digit to a result list each time. If n becomes 1, sort the digits and join them into a string. This implementation is straightforward in Python, Java, C++, and Go with identical logic.

How to solve Smallest Number With Given Digit Product in O(log n)?

Iterate digits from 9 down to 2 and repeatedly divide n while it is divisible by that digit. Store each successful divisor. If the remaining value becomes 1, sort the collected digits in ascending order and concatenate them to form the smallest number. If a leftover factor greater than 1 remains, no valid number exists.

What is the best approach for Smallest Number With Given Digit Product?

The optimal approach uses greedy prime factorization. Repeatedly divide n by digits from 9 down to 2 and store those digits. This compresses prime factors into the fewest digits, which minimizes the resulting number after sorting. The algorithm runs in O(log n) time with O(log n) space for storing digits.

Is Smallest Number With Given Digit Product asked at Google/Amazon/Meta?

Problems involving digit factorization and greedy decomposition appear in interviews at large companies such as Google, Amazon, and Meta. While this exact problem may vary in wording, the underlying concept of compressing prime factors into digits is a common algorithmic pattern.

What data structure is used in Smallest Number With Given Digit Product?

The solution mainly relies on mathematical factorization and a simple list or array to store digits. After collecting the digits, sorting the list ensures the final number is lexicographically smallest. No complex data structures are required.

What is the time complexity of Smallest Number With Given Digit Product?

The greedy factorization solution runs in O(log n) time because each division reduces n multiplicatively. At most log n factor operations occur. Space complexity is O(log n) for storing the digits that form the resulting number.

Description Hints 5 Solution Video 24:30

2847. Smallest Number With Given Digit Product

Medium43.8% acceptance1 companyPremium elsewhere, free here

Given a positive integer n, return a string representing the smallest positive integer such that the product of its digits is equal to n, or "-1" if no such number exists.

Example 1:

Input: n = 105
Output: "357"
Explanation: 3 * 5 * 7 = 105. It can be shown that 357 is the smallest number with a product of digits equal to 105. So the answer would be "357".

Example 2:

Input: n = 7
Output: "7"
Explanation: Since 7 has only one digit, its product of digits would be 7. We will show that 7 is the smallest number with a product of digits equal to 7. Since the product of numbers 1 to 6 is 1 to 6 respectively, so "7" would be the answer.

Example 3:

Input: n = 44
Output: "-1"
Explanation: It can be shown that there is no number such that its product of digits is equal to 44. So the answer would be "-1".

Constraints:

1 <= n <= 10¹⁸

Asked at 1 company

Microsoft

Topics

Greedy Math

Hints open one at a time

Hint 1

Find the prime factors of n.

Hint 2

If there is a prime factor p such that p >= 11, the answer is -1. Since there are no digits whose products equal p.

Hint 3

Factors 5 and 7 should be included in the answer since their product with any number bigger than 1 is a 2-digit number.

Hint 4

For factors 2 and 3, we group every three 2 into an 8 and every two 3 into a 9.

Hint 5

For any leftover 2 or 3, check all the possible combinations.

24:30

Still stuck?Read the written solution, or watch a walkthrough.

Open solution