# Could you anyone offer an elegant solution to deal with 2147483647?

• ``````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)));
}
}
``````

• You could solve it with Math.abs(integerReplacement(n + 1))

• Divide first then add. Check out the updated code below:

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

• This post is deleted!

• 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;
}
};
``````

• ``````    public int integerReplacement(int n) {
int cnt = 0;
while (n > 1) {
if (n % 2 == 0) {
n >>>= 1;
} else if (n <= 3 || (n & 2) == 0){
n -= 1;
}else if (n == Integer.MAX_VALUE) {
n = 1 << 30;
cnt++;
} else {
n += 1;
}
cnt++;
}
return cnt;
}
``````

• Can someone explain why the INT_MAX would return 33 instead of 32 if the hard coded if statement was removed?

• This post is deleted!

• 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;
}
};
``````

• Convert the input to a 64-bit integer first.

• @Davidhunter you can use if(n == Integer.MAX_VALUE) return 32;
Because it is the only case like what you did for n = 1;

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