625.Minimum Factorization

1-Math

class Solution {
    public int smallestFactorization(int a) {
        if(a == 1)
            return 1;
        List<Integer> digit = new ArrayList<>();
        while(a > 1){
            int i = 9;
            for(; i >= 2; i--){
                if(a % i == 0){
                    digit.add(i);
                    a = a / i;
                    break;
                }
            }
            if(i == 1)
                return 0;
        }
        Collections.sort(digit);
        StringBuilder sb = new StringBuilder();
        for(int i : digit)
            sb.append(i);
        Long num = Long.parseLong(sb.toString());
        if(num > Integer.MAX_VALUE)
            return 0;
        return Integer.parseInt(sb.toString());
    }
}

//Better
public class Solution {
    public int smallestFactorization(int n) {
        // Case 1: If number is smaller than 10
        if (n < 10) return n;

        // Case 2: Start with 9 and try every possible digit
        List<Integer> res = new ArrayList<>();
        for (int i = 9; i > 1; i--) {
            // If current digit divides n, then store all
            // occurrences of current digit in res
            while (n % i == 0) {
                n = n / i;
                res.add(i);
            }
        }

        // If n could not be broken in form of digits
        if (n != 1) return 0;

        // Get the result from the array in reverse order
        long result = 0;
        for (int i = res.size() - 1; i >= 0; i--) {
            result = result * 10 + res.get(i);
            if (result > Integer.MAX_VALUE) return 0;
        }

        return (int)result;
    }
}