##### Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/625.html

# 625. Minimum Factorization

Medium

## Description

Given a positive integer a, find the smallest positive integer b whose multiplication of each digit equals to a.

If there is no answer or the answer is not fit in 32-bit signed integer, then return 0.

Example 1

Input:

48


Output:

68


Example 2

Input:

15


Output:

35


## Solution

If a is less than 10, then simply return a. Otherwise, first check the prime factors of a. If there exists a prime factor of a that is greater than 10, then it is impossible to represent a using the multiplication of several one-digit numbers, so return 0.

To find the smallest positive integer b, b must have the shortest length, so consider the maximum possible one-digit factor first. Therefore, loop over i from 9 to 2, and divide a by i until a can’t be divisible by i. Store the factors and append them in the reversing order to form b, and return.

• class Solution {
public int smallestFactorization(int a) {
if (a < 10)
return a;
boolean oneDigitPrime = oneDigitPrime(a);
if (!oneDigitPrime)
return 0;
List<Integer> factors = new ArrayList<Integer>();
int num = a;
for (int i = 9; i > 1 && num > 1; i--) {
while (num % i == 0) {
num /= i;
}
}
if (factors.size() > 10)
return 0;
long newNumLong = 0;
for (int i = factors.size() - 1; i >= 0; i--)
newNumLong = newNumLong * 10 + factors.get(i);
if (newNumLong > Integer.MAX_VALUE)
return 0;
else
return (int) newNumLong;
}

public boolean oneDigitPrime(int num) {
while (num % 2 == 0)
num /= 2;
for (int i = 3; i <= 7 && num > 1; i += 2) {
while (num % i == 0)
num /= i;
}
return num == 1;
}
}

• class Solution(object):
# while loop
def smallestFactorization(self, a):
"""
:type a: int
:rtype: int
"""
if a < 10:
return a
path = []
k = 9
while k > 1 and a > 1:
if a % k == 0:
path.append(str(k))
a /= k
else:
k -= 1
path.sort()
if a > 9 or not path:
return 0
ans = int("".join(path))
return ans if ans <= 0x7fffffff else 0

# normal DFS
def smallestFactorization(self, a):
"""
:type a: int
:rtype: int
"""
if a <= 1:
return a

def dfs(num, path):
if num == 1:
self.ans = min(self.ans, int("".join(sorted(path))))
return True
for i in reversed(range(2, 10)):
if num % i == 0:
path.append(str(i))
if dfs(num / i, path):
return True
path.pop()
return False

self.ans = float("inf")
dfs(a, [])
return self.ans if self.ans != float("inf") and self.ans <= 0x7fffffff else 0


• 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;
}
};

• 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
}