397. Integer Replacement

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

1. If n is even, replace n withn/2. If n is odd, you can replace n with eithern + 1orn - 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

Solution 1: DP. If n is even, f(n) = f(n/2) + 1, if n is odd f(n) = Min(f(n - 1), f(n + 1)) + 1 = Min(f(n - 1), f((n + 1)/2) + 1) + 1. If an array is used, it will get time limit exceed error. But a map can be used to store previous calculated value. Be aware of the potential overflow cause by n + 1.

    public int integerReplacement(int n) {
        Map<Long, Integer> map = new HashMap<>();
        return helper(map, (long)n);
    }

    private int helper(Map<Long, Integer> map, long n) {
        if (n == 1) {
            return 0;
        }
        if (map.containsKey(n)) {
            return map.get(n);
        }
        int res = 0;
        if (n%2 == 0) {
            res = helper(map, n/2) + 1;
        } else {
            res = Math.min(helper(map, n + 1), helper(map, n - 1)) + 1;
        }
        map.put(n, res);
        return res;
    }

Solution 2: bit manipulation. The logic is quite complicated for me. Details see here

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