Python solution with detailed explanation


  • 0
    G

    Solution

    Number Complement https://leetcode.com/problems/number-complement/

    Algorithm

    • Find the index of the first set bit O(32). Simply XOR the input until that bit: O(32).
    class Solution(object):
        def find_last_set_bit(self, num):
            last_set_bit, mask = 0, 1
            for i in range(32):
                if (mask << i) & num:
                    last_set_bit = i
            return last_set_bit
        
        def findComplement(self, num):
            """
            :type num: int
            :rtype: int
            """
            last_set_bit, mask = self.find_last_set_bit(num), 1
            for i in range(last_set_bit+1):
                num = num ^ (mask << i)
            return num
    
    • Find the power of 2 number larger than num. Then i-1 will unset the last set bit and set all bits to its right to 1. Then just XOR with this number.
    class Solution(object):
        def findComplement(self, num):
            """
            :type num: int
            :rtype: int
            """
            i = 1
            while i <= num:
                i = i << 1
            return (i-1)^num
    

  • 0
    H

    @gabbu We can make use of "bit_length()" function of python to eliminate some looping.

    We can do something like this

    class Solution(object):
        def findComplement(self, num):
            """
            :type num: int
            :rtype: int
            """
            msb = num.bit_length()
            return (2**msb-1) ^ num
    

    This uses similar approach as yours just by avoiding loops.


Log in to reply
 

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