Leetcode: Integer Replacement

Given a positive integer n and you can do operations as follow:

If n is even, replace n with n/2.
If n is odd, you can replace n with either n + 1 or n - 1.
What is the minimum number of replacements needed for n to become 1?

Example 1:

Input:
8

Output:
3

Explanation:
8 -> 4 -> 2 -> 1
Example 2:

Input:
7

Output:
4

Explanation:
7 -> 8 -> 4 -> 2 -> 1
or
7 -> 6 -> 3 -> 2 -> 1

Refer to: https://discuss.leetcode.com/topic/58334/a-couple-of-java-solutions-with-explanations/2

When to add 1 instead of minus 1, here is an example:

 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.

 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:

So the logic is:

1. If n is even, halve it.
2. If n=3 or n ends with "01", decrease n
3. Otherwise, increment n.(ends with "11", "111" or even more "1111")

public class Solution {
    public int integerReplacement(int n) {
        int count = 0;
        while (n != 1) {
            if ((n & 1) == 0) 
                n = n >>> 1;
            else if (n==3 || (n & 0b11) == 1)
                n--;
            else n++;
            count++;
        }
        return count;
    }
}

Another logic is:

So the logic is:

1. If n is even, halve it.
2. If n=3 or n-1 has less 1's than n+1, decrement n.
3. Otherwise, increment n.

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