Optimized Backtracking Java AC Solution (Explained)


  • 0

    We try to decompose the problem in form of a tree, starting from the input number that can be branched in 2-9 ways (as the branch with value 1 means the input number itself). Our goal is to find the shortest path from the root to the leaf, while generating the minimal number. We try branching from the highest number first, as then we will construct the shortest path.

    	      48
    	     /|\  
    	    8 6 4.. 2  
    	   /  |  \
    	  6   8  6
                     |
                     2
    

    Also assuming that if a number is divisible by 8, then no need to divide further by 4 and 2 (factors) and this is done by maintaining information about all the previous numbers seen, using a seen variable.

    public int smallestFactorization(int a) {
        if (a <= 1) return a;
        long ans = Long.MAX_VALUE;
            
        int seen = 1;
        for (int idx = 9; idx > 1; idx --) 
            if (seen % idx != 0 && a % idx == 0) {
                seen *= idx;
                int val = smallestFactorization (a/idx);
                if (val > 0) ans = Math.min (ans, val == 1 ? idx : 10l * val + idx);
            }
        
        return (ans == Long.MAX_VALUE || ans > Integer.MAX_VALUE) ? 0 : (int) ans;
    }
    

Log in to reply
 

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