# [LeetCode]Minimum Factorization

## 题目描述：

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:

Output:

Example 2

Input:

Output:

## Python代码：

```class Solution(object):
def smallestFactorization(self, a):
"""
:type a: int
:rtype: int
"""
if a == 1: return 1
cnt = [0] * 10
for x in range(9, 1, -1):
while a % x == 0:
cnt[x] += 1
a /= x
if a > 1: return 0
ans = int(''.join(str(n) * cnt[n] for n in range(2, 10)))
return ans <= 0x7FFFFFFF and ans or 0```

#### 解法II 因式分解

```将a因式分解，若存在大于9的因子，则直接返回0

a的因子包括2, 3, 5, 7四种类型

## Java代码：

```import java.math.BigInteger;

public class Solution {
public int smallestFactorization(int a) {
if (a == 1) return 1;
int cnt[] = new int[10];
while (a > 1) {
for (int x = 2; x  9) return 0;
if (a % x == 0) {
cnt[x]++;
a /= x;
break;
}
}
}
cnt[9] = cnt[3] / 2;
cnt[3] %= 2;
cnt[8] = cnt[2] / 3;
cnt[2] %= 3;
if (cnt[2] > 0 && cnt[3] > 0) {
cnt[2]--;
cnt[3] = 0;
cnt[6] = 1;
}
if (cnt[2] == 2) {
cnt[2] = 0;
cnt[4] = 1;
}
StringBuilder sb = new StringBuilder();
for (int i = 2; i <= 9; i++) {
for (int j = 0; j  0)
return 0;
return Integer.parseInt(ans);
}

}```

|