397.-integer-replacement.md

397. Integer Replacement

• Medium

• 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.

Analysis

This can be solved using a greedy method. If the number is even, we have no choice but to divide it by two. If it is odd, then either n+1 or n-1 will be divisible by 4. We take that because that will help it to shrink faster. The only corner case is at 3 where we take 3-1=2 and 2/2=1.

class Solution(object):
    def integerReplacement(self, n):
        """
        :type n: int
        :rtype: int
        """
        moves = 0
        while n != 1:
            if n % 2 == 0:
                n = n/2
                moves += 1
                continue
            if n == 3:
                return moves + 2
            if (n + 1) % 4 == 0:      
                n = n + 1
            elif (n - 1) % 4 == 0:
                n = n - 1
            moves += 1
        return moves