# Java code, pure Math, with detailed explanation

• ``````public class Solution {
public int smallestFactorization(int a) {
// algorithm 2017/06/19: this is a math problem. Since the question is asking for each digit, we will need to make sure the prime factors can only be 2,3,5,7
// and then can be factored into digits: 2,3,5,7, 4,6,8,9
// key is the make sure the NUMBER of digits are the smallest. Once we get all the digits, we sort them and get the result

// the following algo does not work with the case that 1==a
if (1 == a) {
return 1;
}

int count2s = 0, count3s = 0, count5s = 0, count7s = 0;
while (0 == a % 7) {
count7s++;
a /= 7;
}
while (0 == a % 5) {
count5s++;
a /= 5;
}
while (0 == a % 3) {
count3s++;
a /= 3;
}
while (0 == a % 2) {
count2s++;
a /= 2;
}
if (1 != a) {
return 0;   // a has prime factors larger than 7
}

// 5, 7 cannot be multiplied with 2 or 3 to reach a single digit
// so the only choices are 2, 3, 2*2, 2*3, 2*2*2, 3*3
// to reach a 'smallest' positive, we must reduce the number of digits
// example 2 2 2 3 3 => 89, is better than => 249
// therefore, for 2s, we must always find three 2s and combine them into single digit 8
// that gives us three possibilities: 3n 2s, 3n+1 3s, 3n+2 2s

// if there are 3n 2s, then we simply combine every 2 3s to be a 9, so the final digits are:
//   zero 2,  2m   3s => 9s
//   zero 2,  2m+1 3s => 3, 9s

// if there are 3n+1 2s, or 3n+2 2s, then we need to combine the 2s and 3s to get the smallest NUMBER of digits

// if there are 3n+1 2s, the single 2 can be combined with 3s with the following rule:
//   single 2,  2m 3s   => 2, 9s (NUMBER of digits is m+1)
//   single 2,  2m+1 3s => 6, 9s (NUMBER of digits is m+1)

// if there are 3n+2 2s, the two 2s can be combined with 3s with the following rule:
//   double 2s, 2m 3s   => 4, 9s (NUMBER of digits is m+1)
//   double 2s, 2m+1 3s => 2, 6, 9s

int count2sInResult = 0;
int count3sInResult = 0;
int count4sInResult = 0;
int count5sInResult = count5s;
int count6sInResult = 0;
int count7sInResult = count7s;
int count8sInResult = 0;
int count9sInResult = 0;

count8sInResult = count2s / 3;      // 2X2X2 = 8
count9sInResult = count3s / 2;      // 3X3 = 9
// remaining unused 2s and 3s
count2s         = count2s % 3;      // 0, 1, 2
count3s         = count3s % 2;      // 0, 1

if (0 == count2s) {
// remaining 3: either zero (if even number of 3s, all converted into 9), or one
count3sInResult = count3s;
} else if (1 == count2s) {
if (0 == count3s) {
count2sInResult = 1;    // 2 9..9
} else {
count6sInResult = 1;    // 6 9..9
}
} else {    // 2 == count2s
if (0 == count3s) {
count4sInResult = 1;    // 4 9...9
} else {
count2sInResult = 1;    // 2 6 9...9
count6sInResult = 1;
}
}

StringBuilder builder = new StringBuilder();
for (int index = 0; index < count2sInResult; index++) {
builder.append(2);
}
for (int index = 0; index < count3sInResult; index++) {
builder.append(3);
}
for (int index = 0; index < count4sInResult; index++) {
builder.append(4);
}
for (int index = 0; index < count5sInResult; index++) {
builder.append(5);
}
for (int index = 0; index < count6sInResult; index++) {
builder.append(6);
}
for (int index = 0; index < count7sInResult; index++) {
builder.append(7);
}
for (int index = 0; index < count8sInResult; index++) {
builder.append(8);
}
for (int index = 0; index < count9sInResult; index++) {
builder.append(9);
}

// overflow?
int result = 0;
try {
result = Integer.parseInt(builder.toString());
} catch (Exception ex) {
// overflow
result = 0;
}
return result;
}
}``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.