Skip to content

625. Minimum Factorization πŸ”’

DifficultyMedium

Description

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

 

Example 1:

Input: num = 48
Output: 68

Example 2:

Input: num = 15
Output: 35

 

Constraints:

  • 1 <= num <= 231 - 1

Solutions

Solution 1

Thinking

We must write \(num\) as a product of digits \(2..9\) and form the smallest integer. Searching all factorizations is unnecessary.

Fewer digits and smaller high digits win, so divide by \(9\) down to \(2\) and write factors from the low end. If a remainder greater than \(1\) remains or the value overflows \(32\) bits, return \(0\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution:
    def smallestFactorization(self, num: int) -> int:
        if num < 2:
            return num
        ans, mul = 0, 1
        for i in range(9, 1, -1):
            while num % i == 0:
                num //= i
                ans = mul * i + ans
                mul *= 10
        return ans if num < 2 and ans <= 2**31 - 1 else 0

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution {
    public int smallestFactorization(int num) {
        if (num < 2) {
            return num;
        }
        long ans = 0, mul = 1;
        for (int i = 9; i >= 2; --i) {
            if (num % i == 0) {
                while (num % i == 0) {
                    num /= i;
                    ans = mul * i + ans;
                    mul *= 10;
                }
            }
        }
        return num < 2 && ans <= Integer.MAX_VALUE ? (int) ans : 0;
    }
}

 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 < 2) {
            return num;
        }
        long long ans = 0, mul = 1;
        for (int i = 9; i >= 2; --i) {
            if (num % i == 0) {
                while (num % i == 0) {
                    num /= i;
                    ans = mul * i + ans;
                    mul *= 10;
                }
            }
        }
        return num < 2 && ans <= INT_MAX ? ans : 0;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
func smallestFactorization(num int) int {
    if num < 2 {
        return num
    }
    ans, mul := 0, 1
    for i := 9; i >= 2; i-- {
        if num%i == 0 {
            for num%i == 0 {
                num /= i
                ans = mul*i + ans
                mul *= 10
            }
        }
    }
    if num < 2 && ans <= math.MaxInt32 {
        return ans
    }
    return 0
}

Comments