## 题目描述：

LeetCode 625. 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:

`48 `

Output:

`68`

Example 2
Input:

`15`

Output:

`35`

## 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
``````

```将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 <= a; x++) {
if (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 < cnt[i]; j++) {
sb.append(Integer.toString(i));
}
}
String ans = sb.toString();
if (new BigInteger(ans).compareTo(BigInteger.valueOf(Integer.MAX_VALUE)) > 0)
return 0;
return Integer.parseInt(ans);
}

}
``````

Pingbacks已关闭。