[java/4ms] iterative, greedy, explained in detail.

• if n > 1, you need to divide by 2 to decade faster. No matter you add or minus 1, your target is to make it even and then divide by 2.

Here, if n is even, then divide by 2.

Otherwise, if n is odd, then it depends on m = n / 2. if m is odd, we will add or minus 1 in next step. If m is even, then we will save one step instead.

`However n = 3 is the outlier because the difference of 1 matters, see below.`

For instance: n = 39
m = n / 2 = 19, we can
`39 -> 40 -> 20`
`39 -> 38 -> 19 -> 20 or 18` in the next step.

As you can see, if we use `divide by 2` to mark a step, then for every step, the mid result of choosing + or - 1 will have a difference of 1 (e.g. 20 and 19). We can treat them as if they are of no difference. However 19 will require an extra step in next step.

``````public int integerReplacement(int n) {
int cnt = 0;
while (n > 1) {
cnt++;
if ((n & 1) != 0) {
cnt++;
n >>= 1;
if (n != 1 && (n & 1) != 0) n++;
} else {
n >>= 1;
}
}

return cnt;
}
``````

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