Given a positive integernand 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 fornto 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

class Solution {

    Map<Integer, Integer> hash = new HashMap<>();

    public int integerReplacement(int n) {
        if (n <= 1) return 0;

        hash.put(1, 0);
        hash.put(2, 1);
        return solve(n);
    }

    private int solve(int n){

        if (hash.containsKey(n)) return hash.get(n);

        int cur;

        if (n % 2 == 0){
            cur = solve(n / 2) + 1;   
        }
        else{
            cur = Math.min(solve(1 + (n - 1) / 2) + 2, solve(n - 1) + 1);   
        }

        hash.put(n, cur);

        return cur;
    }
}