Minimum Factorization

Problem

Given a positive integer num, return the smallest positive integerx whose multiplication of each digit equalsnum. If there is no answer or the answer is not fit in 32-bit signed integer, return 0.

Examples

Example 1:

1
2


Input: num = 48
Output: 68

Example 2:

1
2


Input: num = 15
Output: 35

Constraints:

1 <= num <= 2^31 - 1

Solution

Method 1 – Greedy Factorization with Smallest Digits

Intuition

To form the smallest number whose digits multiply to num, we factorize num using digits from 9 down to 2. We use the largest possible digits first to minimize the number of digits, then arrange them in increasing order to get the smallest integer.

Approach

If num is 1, return 1 (since 1 is the only digit).
Try dividing num by digits from 9 to 2, collecting each digit used.
If after all divisions, num is not 1, return 0 (not possible).
Sort the collected digits in increasing order and combine them to form the result.
If the result exceeds 32-bit signed integer, return 0.

Code

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


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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24


func smallestFactorization(num int) int {
    if num == 1 {
        return 1
    }
    ds := []int{}
    for d := 9; d >= 2; d-- {
        for num%d == 0 {
            ds = append(ds, d)
            num /= d
        }
    }
    if num != 1 {
        return 0
    }
    sort.Ints(ds)
    ans := 0
    for _, d := range ds {
        ans = ans*10 + d
        if ans > math.MaxInt32 {
            return 0
        }
    }
    return ans
}

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


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

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


class Solution {
    fun smallestFactorization(num: Int): Int {
        if (num == 1) return 1
        val ds = mutableListOf<Int>()
        var n = num
        for (d in 9 downTo 2) {
            while (n % d == 0) {
                ds.add(d)
                n /= d
            }
        }
        if (n != 1) return 0
        ds.sort()
        var ans = 0L
        for (d in ds) {
            ans = ans * 10 + d
        }
        return if (ans > Int.MAX_VALUE) 0 else ans.toInt()
    }
}

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


def smallest_factorization(num: int) -> int:
    if num == 1:
        return 1
    ds: list[int] = []
    n = num
    for d in range(9, 1, -1):
        while n % d == 0:
            ds.append(d)
            n //= d
    if n != 1:
        return 0
    ds.sort()
    ans = 0
    for d in ds:
        ans = ans * 10 + d
    return ans if ans <= 2**31 - 1 else 0

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


impl Solution {
    pub fn smallest_factorization(num: i32) -> i32 {
        if num == 1 { return 1; }
        let mut ds = vec![];
        let mut n = num;
        for d in (2..=9).rev() {
            while n % d == 0 {
                ds.push(d);
                n /= d;
            }
        }
        if n != 1 { return 0; }
        ds.sort();
        let mut ans: i64 = 0;
        for d in ds {
            ans = ans * 10 + d as i64;
        }
        if ans > i32::MAX as i64 { 0 } else { ans as i32 }
    }
}

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


class Solution {
    smallestFactorization(num: number): number {
        if (num === 1) return 1;
        let ds: number[] = [];
        let n = num;
        for (let d = 9; d >= 2; d--) {
            while (n % d === 0) {
                ds.push(d);
                n /= d;
            }
        }
        if (n !== 1) return 0;
        ds.sort((a, b) => a - b);
        let ans = 0;
        for (let d of ds) {
            ans = ans * 10 + d;
            if (ans > 2147483647) return 0;
        }
        return ans;
    }
}

Complexity

⏰ Time complexity: O(log(num)), since we factorize by digits and build the result.
🧺 Space complexity: O(log(num)), for storing the digits.

Problem#

Examples#

Solution#

Method 1 – Greedy Factorization with Smallest Digits#

Intuition#

Approach#

Code#

Complexity#