Java recursive solution


  • 0
    public int smallestFactorization(int a) {
        PriorityQueue<Integer> q = new PriorityQueue<>();//use priority queue to make sure smaller numbers are before bigger numbers.
        return smallestFactorization(a,q);
    }
    
    private static int smallestFactorization(int residue, PriorityQueue<Integer> q) {
        if(residue < 10) {
            q.add(residue);
            long result = 0L;
            while(!q.isEmpty()) {
                int s = q.poll();
                result = result*10 + s;    
                if(result > Integer.MAX_VALUE) {//handle overflow
                	return 0;
                }
            }
            return (int)result;
        }
        for(int i=9;i>1;--i) {//use bigger factor first, because anything can be divided by 8, can be by 4 and 2.
            if(residue%i ==0) {//a solution is possible so far.
                q.add(i);
                int b = residue/i;
                return smallestFactorization(b,q);
            }
        }
        return 0;
    }

Log in to reply
 

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