Java -- recursion method -- very easy to understand.


  • 0
    J

    In my code, I don't want to deal with negative number. The only way a negative number can occur is when n == Integer.MAX_VALUE, which is 2147483647. When we add 1 to it, it becomes -2147483648. As we know 2^31 = 2147483648, so we just need +1 and keep dividing Integer.MIN_VALUE by 2 for 31 times. Please let me know what you think.

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

Log in to reply
 

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