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 <= 1018We 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).
Java
C++
Go
Remove K digits | Build lowest number | Leetcode #402 • Techdose • 91,163 views views
Watch 9 more video solutions →Practice Smallest Number With Given Digit Product with our built-in code editor and test cases.
Practice on FleetCode