# Two Solutions

1. Naive recursion solution, need to pay attention to overflow:
public int integerReplacement(int n) {
return op((long)n);
}

private int op(long n) {
int result = 0;
while (n > 1) {
if (n % 2 == 1) {
result++;
return result + Math.min(op(n+1), op(n-1));
} else {
n >>= 1;
}
result++;
}
return result;
}

2. A better solution, but a little tricky. In general reducing the number of bits as much as possible in one operation is good since shifting to the right is much faster than +1 or -1. If we analyze +1 and -1 further, we can find out that:

• for consecutive 1s like 111, plus 1 can reduce more 1s
• for patterns end with 01, minus one can reduce one bit while plus one won't affect the number of bits
• Somehow this strategy doesn't seem right for n = 3 since plus one reduce 1 bit but introduce 2 shifts.
• n = Integer.MAX_VALUE will introduce overflow, we can return 32 in this case.
Solution:
public int integerReplacement(int n) {
int result = 0;
if (n == Integer.MAX_VALUE) {
return 32;
}
while (n > 1) {
if ((n & 1) == 1) {
if (n != 3 && (n & 2) == 2) {
n++;
} else {
n--;
}
} else {
n >>= 1;
}
result++;
}
return result;
}

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