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
Example 2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
| public class Solution {
public int smallestFactorization(int a) {
if (a == 1) {
return 1;
}
int[] map = new int[10];
while (a > 1) {
for (int i = 2; i <= a; i++) {
if (i > 9) {
return 0;
}
if (a % i == 0) {
map[i]++;
a /= i;
break;
}
}
}
map[9] += map[3] / 2;
map[3] %= 2;
map[8] += map[2] / 3;
map[2] %= 3;
int min = Math.min(map[2], map[3]);
map[6] += min;
map[2] -= min;
map[3] -= min;
map[4] += map[2] / 2;
map[2] %= 2;
long result = 0L;
for (int i = 2; i <= 9; i++) {
for (int j = 0; j < map[i]; j++) {
result = result * 10 + i;
}
}
if (result > Integer.MAX_VALUE) {
return 0;
}
return (int) result;
}
}
|