[Algorithm] Single Number III

Single Number III

Problem Statement:

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].

Solution 1: Bit manipulation, differential bits.

Well the name of the solution may not reflect or give any hint about how exactly we can solve it. But anyway, it's bit manipulation based, and we can differentiate the array into two sets to find out the two numbers.

Let's first think about this, naturally when we do a xor operation on all the numbers, we can get a ^ b in the end. But this is not enough to tell us what's a and what's b. But xor operation is a differential operation on the two, meaning any difference between a and b will be reflect on the xor result of a and b. And we can make use of that difference to divide the original array, we use the last (closer to LSB) different bit. Suppose we have the following numbers in binary representation:

[0000, 0000, 0010, 0100, 1000, 1000, 1110, 1110, 1101, 1101, 0111, 0111]

The a^b = 0110, and we have bit 1 and bit 2 being different. Now let's divide this array into two sets depending on the bit 1. Then we have:

Bit 1 = 0: [0000, 0000, 0100, 1000, 1000, 1101, 1101]

Bit 1 = 1: [0010, 1110, 1110, 0111, 0111]

Now each set will only have one single number, we can then do a xor operation over the two sets respectively. 

So the key point of this solution is that if we divide the original array by the difference between a and b, we can guarantee that in the two subsets, everything else will appear twice and only one element appear once.

Code implementation:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

class Solution { public: vector<int> singleNumber(vector<int>& nums) { int lump = 0; for (auto v : nums) lump ^= v; int lastSetBit = lump & (-lump); /* last set bit can differentiate a, b*/ int a = 0; int b = 0; for (auto v : nums) { if (v & lastSetBit) { a ^= v; } else { b ^= v; } } return vector<int>{a, b}; } };