Python beats 97%


  • 1

    Idea:
    If n is even, obviously do >> 1.
    If n is odd,
    If n+1 has more leading zeros, do n + 1. Otherwise, do n - 1.

    Here, the one with more leading zeros actually implies it has fewer ones and can be applied by >> 1 more times than n - 1.

    n = 3 is a special case and we do n - 1.

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

  • 0
    C

    Why ((n + 1) & n) > ((n - 1) & (n - 2))?


Log in to reply
 

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