Given an array of integers, every element appears twice except for two. Find that single two.
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?
If you know the xor method of the "Single Number I", please think about the properties of xor of the two numbers.
- x = xor of each element in the list ==> x = a xor b
- a != b => there are at least one 1-bit in x
- take an arbitrary 1-bit (which means a and b is different on this bit), the elements in the array can be classified into two groups: one of them contains a, the other contains b.
- a = xor of each element in the list which the corresponding bit = 0
- b = a xor x