397. Integer Replacement

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

1. If n is even, replace n with n/2.
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

Recursive DFS

这个题的目的是把数字n尽快的通过去掉LSB 得到1

对于偶数直接向右移动一位就可以，但是对于奇数来说，需要+1，或者-1来获得最右边bit为0从而移动。
对于2147483647（01111111 11111111 11111111 11111111）而言，加1会overflow。但是我们可以绕过+1. 通过先把+1和-1的两个偶数／2搞出来，然后加上cost（2）就可以了。

  public int integerReplacement(int n) {  
     if(n<= 1) return 0;  
     if(n%2==0) return 1+integerReplacement(n/2);  
     return 2+Math.min(integerReplacement(n/2),integerReplacement(n/2+1));  
   }  

Tricky 的 iterative 做法

When n is even, the operation is fixed. The only unknown procedure is when it is odd. 

假设奇数n=2k+1, 那么  n+1 = 2k+2 and n-1 = 2k. 

（n+1)/2 = k+1 and (n-1)/2 = k.

说明下一步的两个数一个奇数，一个偶数。And the "best" case of this problem is to divide as much as possible. （Greedy）例如（1110 和 10000 我们选10000）

因此always pick n+1 or n-1 based on if it can be divided by 4

The only special case of that is when n=3 you would like to pick n-1 rather than n+1.

public int integerReplacement(int n) {
    if(n==Integer.MAX_VALUE) return 32; //n = 2^31-1;
    int count = 0;
    while(n>1){
        if(n%2==0) n/=2;
        else{
            if((n+1)%4==0&&(n-1!=2)) n+=1;
            else n-=1;
        }
        count++;
    }
    return count;
}