public int integerReplacement(int n) {
if (n == 1) return 0;
if (n == 2147483647) {
return Math.min(1 + integerReplacement(2147483647  1), 2 + integerReplacement((2147483646 / 2) + 1));
}
if (n % 2 == 0) {
return (1 + integerReplacement(n / 2));
} else {
return (1 + Math.min(integerReplacement(n  1), integerReplacement(n + 1)));
}
}
Could you anyone offer an elegant solution to deal with 2147483647?


For C++, I use
int64_t
to get rid of the boundary problem, without loosing much efficiency.class Solution { public: int integerReplacement(int n) { int64_t nn = n; int step = 0; while (nn > 1LL) { while (nn % 2LL == 0LL) { nn >>= 1LL; ++step; } if (nn == 1LL) return step; if (nn > 3LL && (nn & 2LL)) { ++nn; } else { nn; } ++step; } return step; } };

There are some points to pay attention to deal with INT_MAX
 Notice that /2 will keep the signed bit(MSB)
 For C++, it is implementation dependent to keep MSB or not for shift right
 So just convert int to unsigned and use shift right by 1 instead of /2
C++ code below
class Solution { public: int integerReplacement(int in) { int ret = 0; unsigned n = in; while (n != 1) { if ((n&1) == 0) { n >>= 1; } else { if ((n&2) == 0  n == 3) { n = 1; } else { n += 1; } } ret += 1; } return ret; } };