397. Integer Replacement #

Problem #

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

Problem Statement #

Given a positive integer n, you can do the following operations:

If n is even, replace n with n / 2.
If n is odd, you can replace n with n + 1 or n - 1.

Ask what is the minimum number of replacements needed for n to become 1?

Solution Ideas #

The problem gives an integer n, and then asks us to transform it into 1. If n is even, it can directly become n/2; if it is odd, it can first become n+1 or n-1. Ask for the minimum number of steps to eventually become 1.
When n is odd, when should we add 1 and when should we subtract 1? By observing the pattern, we can find that, except for 3 and 7, all odd numbers that become multiples of 4 after adding 1 are suitable for adding 1 first, such as 15:
```
  15 -> 16 -> 8 -> 4 -> 2 -> 1
  15 -> 14 -> 7 -> 6 -> 3 -> 2 -> 1
    
  111011 -> 111010 -> 11101 -> 11100 -> 1110 -> 111 -> 1000 -> 100 -> 10 -> 1
  111011 -> 111100 -> 11110 -> 1111 -> 10000 -> 1000 -> 100 -> 10 -> 1
```
For 7, the results of adding 1 and subtracting 1 are the same, so it can be ignored. For 3, subtracting 1 takes fewer steps, so this special case needs to be handled first.
Finally, how do we determine whether a number becomes a multiple of 4 after adding 1? Here is a small trick. Since we have previously determined that it is odd, the rightmost bit must be 1. If the second bit from the right is also 1, then after adding 1 and carrying, the two rightmost bits must become 0, so it must be a multiple of 4. Thus it can be determined. The remaining case is the even case. If it was previously determined to be even, then directly divide by 2 (shift right by one bit).

Code #


package leetcode

func integerReplacement(n int) int {
	res := 0
	for n > 1 {
		if (n & 1) == 0 { // Check whether it is even
			n >>= 1
		} else if (n+1)%4 == 0 && n != 3 { // Last 2 bits are 11
			n++
		} else { // Last 2 bits are 01
			n--
		}
		res++
	}
	return res
}