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:
class Solution {
public int smallestFactorization(int a) {
if (a <= 9) return a;
int d = 0;
for (int i = 9; i > 1; i --) {
if (a % i == 0) {
d = i;
break;
}
}
if (d == 0) return 0;
int prev = smallestFactorization(a / d);
if (prev == 0) return 0;
if ((long) prev * 10 + d > Integer.MAX_VALUE) return 0;
return prev * 10 + d;
}
}