Watch 2 video solutions for Smallest Number With Given Digit Product, a medium level problem involving Math, Greedy. This walkthrough by Doctor Lai has 48 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |