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(n1));
Why does INT_MAX return 33 instead of 32 in recursive soln?

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(n1)); } }
So, INT_MAX is a special case if the parameter type is int.