To minimize the number of replacements, we should make `n`

decrease to 1 as soon as possible. In other word, try to make it as even number as many times as possible. Because we can only do either `n+1`

or `n-1`

, the only thing we can do is to make the number divisible by `4`

. Then we can make sure it will fall into even number at least twice in following replacement. `3`

is an exception because it will become to `1`

right after minus `1`

and divide `2`

. `INT_MAX`

is another corner case.

```
class Solution {
public:
int integerReplacement(int n) {
int res = 0;
while (n > 1) {
if (n == INT_MAX) {n >>= 1; n++; res++;}
else if (n&1 && (n == 3 || (n+1)%4)) n--;
else if (n&1) n++;
else n >>= 1;
res++;
}
return res;
}
};
```