Python with explanations (efficient and easy to understand)


  • 1
    A
    1. When n is odd: let n = 2k+1, (n+1)/2 = k+1, (n-1)/2 = k where one is even and the other is odd.
    2. Since we prefer the even result, we prefer n + or - 1 that is divisible by 4.
    3. The corner case is n = 3: subtract by 1.
        def integerReplacement(self, n):
            count = 0
            while n > 1:
                if n % 2 == 0:
                    n /= 2
                else:
                    if n == 3:
                        n -= 1
                    else:
                        if (n + 1) % 4 == 0:
                            n += 1
                        else:
                            n -= 1
                count += 1
            return count
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.