8 line java solution with explanation using recursion and O(1) space beats 90% of submissions


  • 0
    D

    Here the input number that we get , can be of 3 types: Even, Odd or Prime

    Case 1: if n is Even

    The answer will always be minSteps(n/2)+2, here is an example,
    lets say n is 10, we need to find what is minSteps(5), once we get this answer, all we have to do is copy it(1 step) and paste it again(1 step), which is how we will get 2 steps.Try this for any even number and you will see this is the most efficient way to get it.

    Case 2: if n is Odd

    Here we check if n is an odd number which is not prime, if it is, we see that the answer is the sum of of minSteps() of both its factors
    eg: if n is 9= 3 * 3,
    the first factor of 9 which is not 1 is 3, and minSteps(3) is 3
    as 9/3 is also 3, and WKT minSteps(3) is 3, the answer should be 3+3 =6

    eg: if n is 21= 7 * 3
    the first factor of 9 which is not 1 is 3 and minSteps(3) is 3
    as 21/3 is 7, We see that minSteps(7) is 7, the answer should be 3+7 =10

    Case 3: if n is Prime
    Lastly, we see that when n is Prime, the answer is the number itself
    eg: 3->3
    7->7
    11->11

    If you need any further explanations,kindly let me know :)

    class Solution {
        public int minSteps(int n) {
            
            //Base case: if n is 1, return 0
            if(n==1)
                return 0;
            
            //General case: if n is more than 1
            
            //Case 1: if n is even, answer is minSteps(n/2)+2
            if((n % 2)==0)
            {
                return minSteps(n/2)+2;
            }
            
            /*Case 2: to check if n is prime,
            if prime, return the number itself,
            else, return the sum of minSteps() of both its factors*/
            
            for(int i=3;i*i<=n;i+=2)
            {
                //if true, means N is not prime, so return sum of minSteps() of both its factors
                if((n % i)==0)
                    return minSteps(i)+minSteps(n/i);
            }
            
            //N is prime, so return the number itself
            return n;
            
        }
    }
    

Log in to reply
 

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