Problem

Given a positive integer n, return a string representing thesmallest positive integer such that the product of its digits is equal to n , or"-1"if no such number exists.

Examples

Example 1:

1
2
3

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:

1
2
3

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:

1
2
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

Solution

Method 1 – Greedy Factorization from 9 Down

Intuition

To get the smallest number, we want to use the largest possible digits (from 9 down to 2) to factor n, so that the resulting number is as small as possible when the digits are sorted in increasing order.

Approach

  1. If n is 1, return “1” (since 1 is the only number whose product is 1).
  2. For digits from 9 down to 2, repeatedly divide n by the digit as long as possible, collecting the digits used.
  3. If n is not 1 after this process, return “-1” (not possible).
  4. Otherwise, sort the collected digits and return them as a string.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

#include <string>
#include <vector>
using namespace std;
class Solution {
public:
    string smallestNumber(long long n) {
        if (n == 1) return "1";
        vector<int> d;
        for (int i = 9; i >= 2; --i) {
            while (n % i == 0) { d.push_back(i); n /= i; }
        }
        if (n != 1) return "-1";
        sort(d.begin(), d.end());
        string ans;
        for (int x : d) ans += to_string(x);
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

import java.util.*;
class Solution {
    public String smallestNumber(long n) {
        if (n == 1) return "1";
        List<Integer> d = new ArrayList<>();
        for (int i = 9; i >= 2; --i) {
            while (n % i == 0) { d.add(i); n /= i; }
        }
        if (n != 1) return "-1";
        Collections.sort(d);
        StringBuilder ans = new StringBuilder();
        for (int x : d) ans.append(x);
        return ans.toString();
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution:
    def smallestNumber(self, n: int) -> str:
        if n == 1: return "1"
        d = []
        for i in range(9, 1, -1):
            while n % i == 0:
                d.append(i)
                n //= i
        if n != 1: return "-1"
        return ''.join(map(str, sorted(d)))

Complexity

  • ⏰ Time complexity: O(log n), since the number of digits is at most log n and each division is fast.
  • 🧺 Space complexity: O(log n), for storing the digits.