Python constant space solution (Bit Manipulation).


  • 2
    C
    def singleNumber(self, nums):
        bit = [0] * 32
        for num in nums:
            for i in xrange(32):
                bit[i] += num >> i & 1
        res = 0
        for i, val in enumerate(bit):
            # if the single numble is negative,
            # this case should be considered separately 
            if i == 31 and val%3:
                res = -((1<<31)-res)
            else:
                res |= (val%3)*(1<<i)
        return res

  • 1
    C

    A version which does not use extra space:

    def singleNumber(self, nums):
        res = 0
        for i in xrange(32):
            count = 0
            for num in nums:
                count += (num >> i) & 1
            rem = count % 3
            if i == 31 and rem:
                res -= 1 << 31
            else:
                res |= rem * (1 << i)
        return res

  • 0

    Does any one could explain it?
    @caikehe said in Python constant space solution (Bit Manipulation).:

    A version which does not use extra space:

    def singleNumber(self, nums):
        res = 0
        for i in xrange(32):
            count = 0
            for num in nums:
                count += (num >> i) & 1
            rem = count % 3
            if i == 31 and rem:
                res -= 1 << 31
            else:
                res |= rem * (1 << i)
        return res

  • 0

    @sharing-account especially the meaning of "|="


Log in to reply
 

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