[90 ms] VERY EASYJAVA Iteration Solution; Greedy; Iteration;


  • 0
    H

    public class Solution {
    public int smallestFactorization(int a) {

        //Alog thinking: greedy;find each digit from 9 to 2;sort;assemble.
        //time = O(10lgA), space  = O(lgA)
        
        if (a == 1) return 1;
        
        List<Integer> digits = new ArrayList<>();
        while (a > 1) {
            
            int digit = 9;
            for (digit = 9; digit > 1; digit--) {
                if (a % digit == 0) {
                    digits.add(digit);
                    break;
                }
            }
            
            if (digit == 1 || digits.size() > 10) return 0;
            
            a /= digit;
        }
        
        Collections.sort(digits);
        
        long result = 0;
        for (int x: digits) {
            result *= 10;
            result += x;
        }
        
        return result > Integer.MAX_VALUE ? 0 : (int) result;
    }
    

    }


Log in to reply
 

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