Welcome to Subscribe On Youtube

Question

Formatted question description: https://leetcode.ca/all/397.html

Given a positive integer n, you can apply one of the following operations:

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

Return the minimum number of operations needed for n to become 1.

 

Example 1:

Input: n = 8
Output: 3
Explanation: 8 -> 4 -> 2 -> 1

Example 2:

Input: n = 7
Output: 4
Explanation: 7 -> 8 -> 4 -> 2 -> 1
or 7 -> 6 -> 3 -> 2 -> 1

Example 3:

Input: n = 4
Output: 2

 

Constraints:

  • 1 <= n <= 231 - 1

Algorithm

Use iterative solution, then there is a little trick here. When n is odd, when should we add 1 and when should we subtract 1.

By observation, except for 3 and 7, all adding 1 becomes an odd number that is a multiple of 4, which is suitable for adding 1 operation.

For example 15:

15 -> 16 -> 8 -> 4 -> 2 -> 1

15 -> 14 -> 7 -> 6 -> 3 -> 2 -> 1

For 7, the result of adding 1 and subtracting 1 is the same, we can leave it alone, For 3, the step of subtracting 1 is small, so we need to remove this situation.

So how do we know whether a certain number is a multiple of 4 after adding 1,

We can use a little trick. Since we judged it to be an odd number before, then the rightmost digit must be 1. If the second digit on the right is also 1, then add 1 operation. After the carry, there will definitely be two 0s on the right, which must be a multiple of 4. That’s it.

If it was judged to be an even number before, then divide by 2.

Code

  • 
public class Integer_Replacement {

    public static void main(String[] args) {
        Integer_Replacement out = new Integer_Replacement();
        Solution s = out.new Solution();

//        System.out.println(s.integerReplacement(65535));
        System.out.println(7&2); // 111 & 10 => 10
    }

    class Solution {
        public int integerReplacement(int n) {
            long t = n;
            int cnt = 0;
            while (t > 1) {
                ++cnt;
                if ((t & 1) > 0) {
                    if ((t & 2) == 2 && (t != 3)) { // @note: `==2` 111 & 10 => 10
                        ++t;
                    } else {
                        --t;
                    }
                } else {
                    t >>= 1;
                }
            }

            return cnt;
        }
    }
}

############

class Solution {
    public int integerReplacement(int n) {
        int ans = 0;
        while (n != 1) {
            if ((n & 1) == 0) {
                n >>>= 1;
            } else if (n != 3 && (n & 3) == 3) {
                ++n;
            } else {
                --n;
            }
            ++ans;
        }
        return ans;
    }
}

  • class Solution:
    def integerReplacement(self, n: int) -> int:
        ans = 0
        while n != 1:
            if (n & 1) == 0:
                n >>= 1
            elif n != 3 and (n & 3) == 3:
                n += 1
            else:
                n -= 1
            ans += 1
        return ans

############

class Solution(object):
  def integerReplacement(self, n):
    """
    :type n: int
    :rtype: int
    """
    ans = 0
    while n != 1:
      if n == 3:
        n -= 1
      elif n & 1:
        if ((n + 1) & n) <= ((n - 1) & (n - 2)):
          n += 1
        else:
          n -= 1
      else:
        n >>= 1
      ans += 1
    return ans


  • class Solution {
public:
    int integerReplacement(int N) {
        int ans = 0;
        long n = N;
        while (n != 1) {
            if ((n & 1) == 0)
                n >>= 1;
            else if (n != 3 && (n & 3) == 3)
                ++n;
            else
                --n;
            ++ans;
        }
        return ans;
    }
};

  • func integerReplacement(n int) int {
	ans := 0
	for n != 1 {
		if (n & 1) == 0 {
			n >>= 1
		} else if n != 3 && (n&3) == 3 {
			n++
		} else {
			n--
		}
		ans++
	}
	return ans
}

All Problems

All Solutions