Formatted question description: https://leetcode.ca/all/625.html
625. Minimum Factorization
Level
Medium
Description
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
If a
is less than 10, then simply return a
. Otherwise, first check the prime factors of a
. If there exists a prime factor of a
that is greater than 10, then it is impossible to represent a
using the multiplication of several one-digit numbers, so return 0.
To find the smallest positive integer b
, b
must have the shortest length, so consider the maximum possible one-digit factor first. Therefore, loop over i
from 9 to 2, and divide a
by i
until a
can’t be divisible by i
. Store the factors and append them in the reversing order to form b
, and return.
class Solution {
public int smallestFactorization(int a) {
if (a < 10)
return a;
boolean oneDigitPrime = oneDigitPrime(a);
if (!oneDigitPrime)
return 0;
List<Integer> factors = new ArrayList<Integer>();
int num = a;
for (int i = 9; i > 1 && num > 1; i--) {
while (num % i == 0) {
num /= i;
factors.add(i);
}
}
if (factors.size() > 10)
return 0;
long newNumLong = 0;
for (int i = factors.size() - 1; i >= 0; i--)
newNumLong = newNumLong * 10 + factors.get(i);
if (newNumLong > Integer.MAX_VALUE)
return 0;
else
return (int) newNumLong;
}
public boolean oneDigitPrime(int num) {
while (num % 2 == 0)
num /= 2;
for (int i = 3; i <= 7 && num > 1; i += 2) {
while (num % i == 0)
num /= i;
}
return num == 1;
}
}