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 <= 1018Problem Overview: Given an integer n, build the smallest possible number whose digits multiply to exactly n. Each digit must be between 1 and 9. If no such number exists, return -1. The challenge is minimizing the resulting number while preserving the required digit product.
Approach 1: Brute Force Enumeration (Exponential Time)
Generate candidate numbers and check whether the product of their digits equals n. You compute the digit product by iterating through each digit and multiplying them. The smallest valid candidate is returned. This approach is impractical because the search space grows exponentially with the number of digits. Time complexity is O(10^k) where k is the digit length explored, and space complexity is O(1) aside from candidate generation.
Approach 2: Prime Factorization + Greedy (Optimal, O(log n))
Digits 2–9 are composite representations of prime factors 2, 3, 5, 7. Instead of searching numbers, factorize n using the largest possible digit values from 9 down to 2. For each digit d, repeatedly divide n while n % d == 0 and record d in the result. This greedy step compresses multiple prime factors into a single digit (for example, 8 = 2×2×2, 9 = 3×3), reducing the total number of digits and therefore the final number size.
After extracting all factors, check if n became 1. If not, the product requires a prime factor larger than 7, which cannot be represented by a single digit, so the answer is -1. Otherwise, sort the collected digits in ascending order and concatenate them. Sorting ensures the smallest possible numeric value. The factorization loop runs at most log n times, giving O(log n) time complexity and O(log n) space for storing digits.
This strategy combines math reasoning with a greedy choice. The key observation: larger digits compress factors more efficiently, while sorting at the end guarantees the smallest number.
Recommended for interviews: The greedy factorization approach is the expected solution. It shows you recognize the relationship between digits and prime factors and know how to compress factors optimally. Mentioning brute force first demonstrates problem exploration, but implementing the greedy method proves algorithmic maturity and strong mathematical reasoning.
We consider prime factorizing the number n. If there are prime factors greater than 9 in n, then it is impossible to find a number that meets the conditions, because prime factors greater than 9 cannot be obtained by multiplying numbers from 1 to 9. For example, 11 cannot be obtained by multiplying numbers from 1 to 9. Therefore, we only need to consider whether there are prime factors greater than 9 in n. If there are, return -1 directly.
Otherwise, if the prime factors include 7 and 5, then the number n can first be decomposed into several 7s and 5s. Two 3s can be combined into a 9, three 2s can be combined into an 8, and a 2 and a 3 can be combined into a 6. Therefore, we only need to decompose the number into numbers from 2 to 9. We can use a greedy method, preferentially decomposing into 9, then decomposing into 8, and so on.
The time complexity is O(log n), and the space complexity is O(1).
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Enumeration | O(10^k) | O(1) | Conceptual baseline to understand the problem; not practical for real constraints |
| Prime Factorization + Greedy | O(log n) | O(log n) | General and optimal solution; preferred in interviews and competitive programming |
Day 629 - Teaching Kids Programming - Smallest Number With Given Digit Product (Greedy Factorization • Doctor Lai • 48 views views
Watch 1 more video solutions →Practice Smallest Number With Given Digit Product with our built-in code editor and test cases.
Practice on FleetCode