Question

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

 397	Integer Replacement

 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

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

Java

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

All Problems

All Solutions