Why does INT_MAX return 33 instead of 32 in recursive soln?


  • 0
    S
    int integerReplacement(int n) {
        if (n == 1) return 0;
        if (n < 0) return INT_MAX;
        //if (n == INT_MAX) return 32; 
        //WHY IS THIS NECESSARY?
        
        if (n % 2 == 0)
            return 1 + (integerReplacement(n/2));
        else
            return 1 + min(integerReplacement(n+1), integerReplacement(n-1));

  • 0
    F

    That's because the value of integerReplacement( INT_MAX + 1) is 32, and the value of integerReplacement( INT_MAX - 1) is 33.

    The value of (INT_MAX + 1) exceeds the INT_MAX value, it can't be the parameter of the integerReplacement(int n) function.

    If you use java and change the function parameter type and return value type to "long", you'll get the right answer "32".

    the code is like this,

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

    So, INT_MAX is a special case if the parameter type is int.


Log in to reply
 

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