Extremely simple Java solution


  • 0
    L
    //4 : 1+1+integerReplacement(1)
        public int integerReplacement(int n) {
            if(n<=1) {
                return 0;
            }
            int count=Integer.MAX_VALUE;
            if(n%2==0) {
                count = 1 + integerReplacement(n/2);
            }
            else {
                if(n==Integer.MAX_VALUE) {
                    count = integerReplacement(n-1);
                }
                else {
                    count =1+ Math.min(integerReplacement(n-1),
                    integerReplacement(n+1));
                }
            }
            
            return count;
        }
    

  • 0
    S

    @labs said in Extremely simple Java solution:

    public int integerReplacement(int n) {
    if(n<=1) {
    return 0;
    }
    int count=Integer.MAX_VALUE;
    if(n%2==0) {
    count = 1 + integerReplacement(n/2);
    }
    else {
    if(n==Integer.MAX_VALUE) {
    count = integerReplacement(n-1);
    }
    else {
    count =1+ Math.min(integerReplacement(n-1),
    integerReplacement(n+1));
    }
    }

        return count;
    }
    

    In case where n == Integer.MAX_VALUE, why didn't you add 1. When you are recursively calling integerReplacement(n-1), you have taken one step by subtracting 1. So, in my opinion, 1 should be added. Correct me if I am wrong.


  • 0
    L

    @satvirgrewal Hi..the constraint is :

    If n is even, replace n with n/2.
    If n is odd, you can replace n with either n + 1 or n - 1.
    

    The max_value is an odd number so the idea is to get an even number below it. If you add 1 to it, it will overflow. Let me know if you have any further questions on this solution.


  • 0
    S

    @labs Thanks for the prompt response.
    I agree with the constraint explanation. When we have the max value, we definitely should not add 1 as it will cause overflow. So we are left with subtracting one. Fine till this point.
    But when we have the input as the MAX_VALUE, we subtract 1 out of it and calls the method again. So the call will get us the steps taken for MAX_VALUE-1. But in the above solution, we are not counting the very first step taken, i.e. subtracting 1 from MAX_INTEGER.
    With the above solution,
    2147483647 and 2147483646 will take the same number of steps in reaching to 1. I think 2147483647 will need one more step compared to 2147483646.


  • 0
    L

    @satvirgrewal Very good point! I remember having it like 1+the count as you mentioned. After getting it wrong, my understanding was -- a count of 1 means either n/2 or figuring out n+1 or n-1. Since we don't have a selection between n-1 and n+1 for this particular case, picking n-1 doesn't count as an additional step. This is how I interpreted and I may be wrong too.


Log in to reply
 

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