Java recursive solution with explanation


  • 2

    m represents the no of chars on screen. clip represents the no of chars in the clipboard.
    At every step, we either copy the screen or paste. We have to take the min of these two operations recursively to get the result.

    public class Solution {
        public int minSteps(int n) {
            //consider the 1st step done as there is only one possible - ie copy
            return n == 1 ? 0 : 1 + minSteps(1, 1, n);
        }
        
        private int minSteps(int m, int clip, int n) {
            if(m == n) {
                return 0;
            }
            
            if(m > n) {
    	    // -1 signals that the key sequence followed so far is invalid
                return -1;
            }
            
            if(m == clip) {
    	    //avoid a sequence with consecutive copies
                int pasteCost = minSteps(m + clip, clip, n);
                return pasteCost == -1 ? -1 : 1 + pasteCost;
            }
            
            int copyCost = minSteps(m, m, n);
            int pasteCost = minSteps(m + clip, clip, n);
            if(copyCost == -1 && pasteCost == -1) {
                return -1;
            }
            else if(copyCost == -1) {
                return 1 + pasteCost;
            }
            else if(pasteCost == -1) {
                return 1 + copyCost;
            }
            else {
                return 1 + Math.min(copyCost, pasteCost);    
            }
        }
    }
    

Log in to reply
 

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