given an array of numbers nums in which exactly two elements appear only once and all the other elements appear exactly twice find the two elements that appear only once limitation time complexity on and space complexity o1 for example given nums 1 2 1 3 2 5 return 3 5 note the order of the result is not important so in the above example 5 3 is also correct solution 1 use xor to cancel out the pairs and isolate ab 2 it is guaranteed that at least 1 bit exists in ab since a and b are different numbers ex 010 111 101 3 single out one bit r right most bit in this solution to use it as a pivot 4 divide all numbers into two groups one group with a bit in the position r one group without a bit in the position r 5 use the same strategy we used in step 1 to isolate a and b from each group type nums listint rtype listint isolate ab from pairs using xor isolate right most bit from ab isolate a and b from ab type nums list int rtype list int isolate a b from pairs using xor isolate right most bit from a b isolate a and b from a b
def single_number3(nums):
    
    
    ab = 0
    for n in nums:
        ab ^= n

    
    right_most = ab & (-ab)

    
    a, b = 0, 0
    for n in nums:
        if n & right_most:
            a ^= n
        else:
            b ^= n
    return [a, b]