leetcode Question: Single Number III

Single Number III

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.

For example:

Given nums = [1, 2, 1, 3, 2, 5], return [3, 5].

Note:

1. The order of the result is not important. So in the above example, [5, 3] is also correct.
2. Your algorithm should run in linear runtime complexity. Could you implement it using only constant space complexity?

Analysis:

From the previous questions we know that the bit manipulation would be a good start to go, same as this problem. The hard part is by XOR all the values in the array, we only have the XOR of the two numbers we have, say  x = a^b. 

From the figure I draw below, it is easy to see that:   the essential usage of XOR operation is to check whether the corresponding bits are same or not between two numbers. In other words, if there is any one bit between the two numbers is set to ‘1’  (e.g., any one bit in x is '1’), the two numbers (e.g., a and b) are impossible to be the same.

Let’s extend the above conclusion to this problem:

1. We have a serise of numbers. 
   
2. We have value x = a ^ b, but we don’t know which two numbers are a and b.
   
3. But we know, there must be at least one bit in a and b are NOT the same. (because x is NOT 0, there must be at least one bit in x is 1)
   
4. In other words, in a certain bit, say kth bit, a must be 0 and b must be 1, or vice versa.
5. Look at the array, every number in the array may be a, or b.
   
6. For every number in the array，look at the kth bit , it has only two possible values: 0 or 1.
7. So if we divide the number in the arrary simplely by the kth bit, the array is divided into two part, and a and b must be in different part.
8. For each part, except the number a (or b), all the other numbers must appear twice in the same part.
9. Now the problem becomes the simple version of single number we have seen before.
10. Done.

Therefore, we have successfully transit the problem into two sub problems, in which a simple loop with XOR operations will work well to solve.

Code (C++):

class Solution {

public:

vector<int> singleNumber(vector<int>& nums) {

vector<int> result(2,0);

int xor_res = 0;

for (int i = 0; i < nums.size();++i){

xor_res ^= nums[i];

}

int mask = xor_res ^ ( xor_res & (xor_res-1) );

int p=0;

int q=0;

for (int i=0;i<nums.size();++i){

if ( (nums[i] & mask) == 0){

p ^= nums[i];

}else{

q ^= nums[i];

}

}

result[0] = p;

result[1] = q;

return result;

}

};

Code (Python):

class Solution(object):

def singleNumber(self, nums):

"""

:type nums: List[int]

:rtype: List[int]

"""

r = 0

for num in nums:

r ^= num

mask = r ^ ( r & (r-1) )

p = 0

q = 0

for num in nums:

if (num & mask) == 0:

p ^= num

else:

q ^= num

return [p ,q]