Problem Description

Given a positive integer num, your task is to find the smallest positive integer whose multiplication of its digits equals num. If there is no such integer, return -1.

• Each digit in the answer must be in the range 2 to 9 (inclusive).
• If there are multiple valid numbers, you must return the smallest one (in terms of integer value, not the number of digits).
• If num is a single-digit number, return num itself.
• Do not use the digit 1, and do not use zero.
• Return -1 if it is impossible to factor num using only digits 2-9.

Example:
Input: num = 48
Output: 68
Explanation: 6 * 8 = 48, and 68 is the smallest such number.

Thought Process

To solve this problem, we need to "reverse" the process of multiplying digits to get num. Instead of multiplying digits to get a product, we want to decompose num into a sequence of digits (2-9) whose product is num. The brute-force way would be to try all possible combinations of digits 2-9, but this quickly becomes infeasible for large num.

We need to find a way to break num into a product of allowed digits, using as few digits as possible (since fewer, larger digits will give a smaller final integer). We should favor larger digits (like 9, 8, 7, etc.) first, but to get the smallest integer, we should actually use the smallest digits possible in the most significant positions (leftmost).

The key insight is to factor num by repeatedly dividing it by the largest possible digit (starting from 9 down to 2), collecting those digits, and finally sorting them to form the smallest integer possible.

Solution Approach

• Step 1: If num is less than 10, return num itself. Single-digit numbers are already their own smallest factorization.
• Step 2: For numbers >= 10, try to divide num by digits from 9 down to 2. For each digit d, while num is divisible by d, divide num by d and store d in a list.
• Step 3: If after all divisions num is greater than 1, it means there are leftover prime factors that can't be represented by digits 2-9, so return -1.
• Step 4: Otherwise, sort the collected digits in ascending order and join them to form the smallest possible integer.
• Step 5: Return that integer as the answer.

This approach ensures we use the smallest possible digits in the highest place values, resulting in the minimum integer.

Example Walkthrough

Let's work through the example where num = 48:

1. Start with 48.
2. Try dividing by 9: 48 / 9 = 5.33... (not integer)
3. Try dividing by 8: 48 / 8 = 6. Collect 8.
4. Now num = 6.
5. Try dividing by 8 again: 6 / 8 = 0.75 (not integer)
6. Try dividing by 7: 6 / 7 = 0.857 (not integer)
7. Try dividing by 6: 6 / 6 = 1. Collect 6.
8. Now num = 1.
9. Since num is now 1, we stop. The collected digits are [8, 6].
10. Sort the digits: [6, 8].
11. Join to form 68. This is the smallest integer whose digits multiply to 48.

Time and Space Complexity

• Brute-force Approach: Trying all combinations of digits 2-9 is exponential time (O(9^k), where k is the number of digits in the answer). This is infeasible for large num.
• Optimized Approach: The factorization loop runs at most log₂(num) times (since we keep dividing), and for each digit 9-2 (constant number of digits), so it's O(log(num)) time.
• Space Complexity: We store at most log₂(num) digits, so space is O(log(num)).

The optimized solution is efficient and suitable for the problem's constraints.

Summary

The Minimum Factorization problem is a clever exercise in reverse factorization using only digits 2-9. The key is to decompose num by dividing by the largest usable digits, then arranging the resulting digits in ascending order to get the smallest possible integer. This approach is both efficient and elegant, avoiding brute-force enumeration and leveraging basic properties of multiplication and digit placement.

Code Implementation

class Solution:
    def smallestFactorization(self, num: int) -> int:
        if num < 10:
            return num
        res = []
        for d in range(9, 1, -1):
            while num % d == 0:
                res.append(d)
                num //= d
        if num != 1:
            return -1
        res.sort()
        ans = int(''.join(map(str, res)))
        return ans if ans <= 2**31 - 1 else 0
    

class Solution {
public:
    int smallestFactorization(int num) {
        if (num < 10) return num;
        vector<int> res;
        for (int d = 9; d >= 2; --d) {
            while (num % d == 0) {
                res.push_back(d);
                num /= d;
            }
        }
        if (num != 1) return -1;
        sort(res.begin(), res.end());
        long long ans = 0;
        for (int d : res) {
            ans = ans * 10 + d;
            if (ans > INT_MAX) return 0;
        }
        return (int)ans;
    }
};
    

class Solution {
    public int smallestFactorization(int num) {
        if (num < 10) return num;
        List<Integer> res = new ArrayList<>();
        for (int d = 9; d >= 2; --d) {
            while (num % d == 0) {
                res.add(d);
                num /= d;
            }
        }
        if (num != 1) return -1;
        Collections.sort(res);
        long ans = 0;
        for (int d : res) {
            ans = ans * 10 + d;
            if (ans > Integer.MAX_VALUE) return 0;
        }
        return (int)ans;
    }
}
    

var smallestFactorization = function(num) {
    if (num < 10) return num;
    let res = [];
    for (let d = 9; d >= 2; --d) {
        while (num % d === 0) {
            res.push(d);
            num = Math.floor(num / d);
        }
    }
    if (num !== 1) return -1;
    res.sort((a, b) => a - b);
    let ans = parseInt(res.join(''), 10);
    return ans <= 0x7FFFFFFF ? ans : 0;
};