Given a positive integer num, return the smallest positive integer x whose multiplication of each digit equals num. If there is no answer or the answer is not fit in 32-bit signed integer, return 0.
Example 1:
Input: num = 48 Output: 68
Example 2:
Input: num = 15 Output: 35
Constraints:
1 <= num <= 231 - 1Problem Overview: Given a positive integer a, construct the smallest positive integer whose digits multiply to a. If no such integer exists or the result exceeds a 32-bit signed integer, return 0.
Approach 1: Brute Force Search (Exponential Time, O(1) Space)
The direct idea is to try integers starting from 1, compute the product of their digits, and check if it equals a. For each candidate number, iterate through its digits and multiply them together. The first valid match is the smallest number because numbers are checked in increasing order. This approach is impractical because the search space grows extremely fast, making the time complexity exponential relative to the number of digits.
Approach 2: Greedy Digit Factorization (O(log a) Time, O(log a) Space)
The key observation: any valid number must be composed of digits 2 to 9 whose product equals a. Instead of searching numbers, factor a using the largest digits first. Iterate from digit 9 down to 2, repeatedly dividing a whenever the digit is a factor. Each successful division adds that digit to the result. Using larger digits first reduces the total digit count, which guarantees the final number is minimal once digits are reversed into ascending order.
If after factoring a the remainder is greater than 1, no valid digit combination exists and the answer is 0. Finally, rebuild the number from the collected digits and verify it fits within the 32‑bit signed integer range.
This solution relies on math properties of factorization and a simple greedy strategy: always pick the largest valid digit to minimize the resulting integer length. The number of divisions is bounded by the number of factors, which is roughly O(log a).
Recommended for interviews: The greedy factorization approach. Interviewers expect you to recognize that digit products correspond to factors between 2 and 9. Starting from 9 ensures fewer digits, which directly produces the smallest numeric value after reversing. Mentioning the brute force idea briefly shows you considered the naive search before optimizing with a greedy mathematical insight.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Search | Exponential | O(1) | Conceptual baseline to understand the problem; not practical for large values |
| Greedy Digit Factorization | O(log a) | O(log a) | Optimal solution for production or interviews; uses digit factors 9→2 to minimize result length |
625. Minimum Factorization (Leetcode Medium) • Programming Live with Larry • 451 views views
Watch 1 more video solutions →Practice Minimum Factorization with our built-in code editor and test cases.
Practice on FleetCode