LeetCode 2847. Smallest Number With Given Digit Product Solution in Java, C++, Python & Go | Explanation + Code

Description

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 <= 1018

Solutions

Solution 1: Prime Factorization + Greedy

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).

PythonJavaC++Go

class Solution: def smallestNumber(self, n: int) -> str: cnt = [0] * 10 for i in range(9, 1, -1): while n % i == 0: n //= i cnt[i] += 1 if n > 1: return "-1" ans = "".join(str(i) * cnt[i] for i in range(2, 10)) return ans if ans else "1"(code-box)

class Solution { public String smallestNumber(long n) { int[] cnt = new int[10]; for (int i = 9; i > 1; --i) { while (n % i == 0) { ++cnt[i]; n /= i; } } if (n > 1) { return "-1"; } StringBuilder sb = new StringBuilder(); for (int i = 2; i < 10; ++i) { while (cnt[i] > 0) { sb.append(i); --cnt[i]; } } String ans = sb.toString(); return ans.isEmpty() ? "1" : ans; } }(code-box)

class Solution { public: string smallestNumber(long long n) { int cnt[10]{}; for (int i = 9; i > 1; --i) { while (n % i == 0) { n /= i; ++cnt[i]; } } if (n > 1) { return "-1"; } string ans; for (int i = 2; i < 10; ++i) { ans += string(cnt[i], '0' + i); } return ans == "" ? "1" : ans; } };(code-box)

func smallestNumber(n int64) string { cnt := [10]int{} for i := 9; i > 1; i-- { for n%int64(i) == 0 { cnt[i]++ n /= int64(i) } } if n != 1 { return "-1" } sb := &strings.Builder{} for i := 2; i < 10; i++ { for j := 0; j < cnt[i]; j++ { sb.WriteByte(byte(i) + '0') } } ans := sb.String() if len(ans) > 0 { return ans } return "1" }(code-box)