I really think it should be tagged medium because there are many subtleties and good understanding of binary arithmetic is required.

The first step towards solution is to realize that you're allowed to remove the LSB only if it's zero. And to reach the target as fast as possible, removing digits is the best way to go. Hence, even numbers are better than odd. This is quite obvious.

What is not so obvious is what to do with odd numbers. One may think that you just need to remove as many 1's as possible to increase the evenness of the number. Wrong! Look at this example:

```
111011 -> 111010 -> 11101 -> 11100 -> 1110 -> 111 -> 1000 -> 100 -> 10 -> 1
```

And yet, this is not the best way because

```
111011 -> 111100 -> 11110 -> 1111 -> 10000 -> 1000 -> 100 -> 10 -> 1
```

See? Both `111011 -> 111010`

and `111011 -> 111100`

remove the same number of 1's, but the second way is better.

So, we just need to remove as many 1's as possible, doing +1 in case of a tie? Not quite. The infamous test with n=3 fails for that strategy because `11 -> 10 -> 1`

is better than `11 -> 100 -> 10 -> 1`

. Fortunately, that's the only exception (or at least I can't think of any other, and there are none in the tests).

So the logic is:

- If
`n`

is even, halve it. - If
`n=3`

or`n-1`

has less 1's than`n+1`

, decrement`n`

. - Otherwise, increment
`n`

.

Here is an example of such a solution in Java:

```
public int integerReplacement(int n) {
int c = 0;
while (n != 1) {
if ((n & 1) == 0) {
n >>>= 1;
} else if (n == 3 || Integer.bitCount(n + 1) > Integer.bitCount(n - 1)) {
--n;
} else {
++n;
}
++c;
}
return c;
}
```

Of course, doing `bitCount`

on every iteration is not the best way. It is enough to examine the last two digits to figure out whether incrementing or decrementing will give more 1's. Indeed, if a number ends with 01, then certainly decrementing is the way to go. Otherwise, if it ends with 11, then certainly incrementing is at least as good as decrementing (`*011 -> *010 / *100`

) or even better (if there are three or more 1's). This leads to the following solution:

```
public int integerReplacement(int n) {
int c = 0;
while (n != 1) {
if ((n & 1) == 0) {
n >>>= 1;
} else if (n == 3 || ((n >>> 1) & 1) == 0) {
--n;
} else {
++n;
}
++c;
}
return c;
}
```

An alternative approach to intuitive algorithm was very well put by @dettier in a discussion: you should create as many trailing zeroes as you can. This way you can avoid the tie-breaking trap (there can be no ties), but you'll still have to handle the n=3 exception separately.