Python 100% Bit manipulation Greedy approach


  • 0

    whenever our current value n is odd, we can calculate a 'cost function' of both n+1 and n-1 where each unset bit has a weight of 1 (since we can just // 2) and each set bit has a weight of 2 (since we either need to +1 or -1 then // 2). If the two cost functions yield the same cost we can just take the value that has a higher right most set bit since this indicates we've cancelled out more 1's.

    I believe the time and space complexity will be both O(1) for 32 bit integers as we'd be running the while loop 32 times at most and each loop will be doing constant time bound operations (count set bits should be a constant operation since iterating through 32bits at most and generating binary string should also be generating a string of length 32 at most). Please correct me if I'm wrong.

        def integerReplacement(self, n):
    
            def cost(n):
                b = bin(n)
                return (2 * b.count('1') + len(b) - 4)
            
            itr = 0
            while n > 1:
                if not n & 1: 
                    n >>= 1
                else:
                    cost_up, cost_down = cost(n+1), cost(n-1)
                    if cost_up < cost_down or (cost_up == cost_down and n+1 & -(n+1) > n-1 & -(n-1)):
                        n += 1
                    else:
                        n -= 1
                itr += 1
            return itr
    

Log in to reply
 

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