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:

1
2
3
4
5
6
7
8
Input:
8
Output:
3
Explanation:
8 -> 4 -> 2 -> 1

Example 2:

1
2
3
4
5
6
7
8
9
10
Input:
7
Output:
4
Explanation:
7 -> 8 -> 4 -> 2 -> 1
or
7 -> 6 -> 3 -> 2 -> 1

Bit Manipulation

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

这个题目标的难度是easy, 但是做起来完全没有那么easy。不太好想到。

  1. n 是偶数，n = n / 2
  2. n 是奇数，就要判断什么时候+1好，什么时候-1好。
    • 若n的最低两位数为01，则令n = n - 1
    • 若n的最低两位数为11，则令n = n + 1
    • 这样处理是为了使n的二进制表式中1的数目尽可能少，从而减少迭代次数
    • 需要注意的是，当n = 3时，不满足上述判定条件，需要单独处理。 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
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;
}

递归

1
2
3
4
5
6
7
8
9
public int integerReplacement(int n) {
    if (n == 1)
        return 0;
    if ((n & 1) == 0) {
        return integerReplacement(n >>> 1) + 1;
    } else {
        return Math.min(integerReplacement(n + 1), integerReplacement(n - 1)) + 1;
    }
}