Skip to content

2847. Smallest Number With Given Digit Product πŸ”’

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 \(7\)s and \(5\)s. Two \(3\)s can be combined into a \(9\), three \(2\)s 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)\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
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"

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
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;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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"
}

Comments