Single Number III

Problem: Single Number III

The two single numbers must be different at least 1 bit, or they will be duplicate numbers, which means one single number values 1 at this bit while the other one values 0. Thus we can try to divide all the numbers into 2 groups by value at this bit and treat the problem as simple Single Number.

We need to first find this important bit. We can xor all the numbers and find the last bit values 1, which means it's the bit we want. We store the position and use AND operation to find whether a number value 1 at this position and get 2 groups. Then we can solve the problem.

Code in Python:

class Solution(object):
    def singleNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        xor = 0
        for n in nums:
            xor ^= n
        i = 0
        while not xor & 1:
            xor >>= 1
            i += 1
        tmp = 1 << i
        a, b = 0, 0
        for n in nums:
            if n & tmp:
                a ^= n
            else:
                b ^= n
        return [a, b]