Minimum Factorization
Problem
Find the smallest positive integer whose digit-product equals n; return 0 if no such integer fits in 32 bits.
n = 4868def smallest_factorization(n):
if n < 2: return n
digits = []
for d in range(9, 1, -1):
while n % d == 0: digits.append(d); n //= d
if n != 1: return 0
digits.sort(); v = int(''.join(map(str, digits)))
return v if v < 2**31 else 0function smallestFactorization(n) {
if (n < 2) return n;
const digits = [];
for (let d = 9; d > 1; d--) while (n % d === 0) { digits.push(d); n = n / d; }
if (n !== 1) return 0;
digits.sort(); const v = Number(digits.join(''));
return v < 2**31 ? v : 0;
}int smallestFactorization(int n) {
if (n < 2) return n;
List ds = new ArrayList<>();
for (int d = 9; d > 1; d--) while (n % d == 0) { ds.add(d); n /= d; }
if (n != 1) return 0;
Collections.sort(ds);
long v = 0; for (int d : ds) v = v * 10 + d;
return v < (1L << 31) ? (int) v : 0;
} int smallestFactorization(int n) {
if (n < 2) return n;
vector ds;
for (int d = 9; d > 1; d--) while (n % d == 0) { ds.push_back(d); n /= d; }
if (n != 1) return 0;
sort(ds.begin(), ds.end());
long long v = 0; for (int d : ds) v = v * 10 + d;
return v < (1LL << 31) ? (int) v : 0;
} Explanation
We need the smallest number whose digits multiply to n. Since each digit is between 1 and 9, this becomes: break n into factors that are single digits, then arrange them into the smallest possible number.
To make a number small, two things help: use as few digits as possible, and put smaller digits in front. Using big factors (like 9, 8) packs more of n into each digit, which keeps the digit count low. So we greedily try to divide out the largest digits first, looping d from 9 down to 2.
For each d, while n is divisible by it, we record d as a digit and divide n by it. If at the end n is not 1, it has a prime factor bigger than 9 (like 11 or 13) that no single digit can cover, so we return 0.
Finally we sort the collected digits ascending and stick them together — smallest digit leftmost gives the smallest number. We also return 0 if it overflows 32 bits.
Example: n = 48. 9 doesn't divide it. 8 does, leaving 6; then 6 divides 6, leaving 1. Digits are [8, 6], sorted to [6, 8], giving 68.