Today’s Leetcode July Challenge, Single Number III, is a real treat. It’s a simple problem with an interesting solution where we get to use some clever bit manipulation to create a very efficient algorithm. The gist of the problem is that we are given an array of numbers where every number occurs twice, except for two numbers which only appear once. Our task is to find and return the two numbers that only appear once. There’s a problem constraint that the algorithm have linear runtime complexity, and a challenge to implement the algorithm with constant space complexity. Here’s an example to clarify the problem description:

Input: [3,1,5,4,3,5] Output: [1,4]

Now, if you’re in a hurry and just looking to get this problem solved, the clear solution is to use a hashmap to count occurences of each number, then iterate over the map and select the two numbers with a single occurence to return. Like so:

vector<int> singleNumber(vector<int>& nums) {
   unordered_map<int,int> m;
   for(const auto num : nums) {
	  m[num]++;
   }
   vector<int> singleNumbers;
   for(const auto [num, count] : m) {
	  if(count == 1) {
		 singleNumbers.push_back(num);
	  }
   }
   return singleNumbers;
}

That works great!..but it’s not very interesting, which is where the challenge constraint of having constant space complexity comes in. In order to achieve this, we’ll use bit manipulation to build a bitmask which will filter out just the two single occurrence numbers. We build the bitmask filter in two steps. The first step could be called exclusive or–xor–accumulation, wherein we begin with a bitmask of 0 and take the binary xor of the bitmask and every subsequent number in the array which results in the exclusive or of the two single occurrence numbers. This is attributable to the fact that any number which occurs an even number of times, twice in this instance, will zero itself in a xor accumulation by the fact that for some digit n, n ^ n = 0. For our example, it looks like this–32-bit integers reduced to 4 bit representation for ease of visualization:

Input: [3,1,5,4,3,5]
bitmask	number			binary_number		bitmask ^ binary_number
[0000]		3			[0011]			[0011]
[0011]		1			[0001]			[0010]
[0010]		5			[0101]			[0111]
[0111]		4			[0100]			[0011]
[0011]		3			[0011]			[0000]
[0000]		5			[0101]			[0101]

[0101] = 1[0001] ^ 4[0100]

Cool! We now have the xor of the two single occurence numbers as a bitmask, but we’re not done yet. In order to turn the bitmask into a filter, we need to select a bit that occurs in one of the single number but not in the other. There are a few ways to achieve this, as any single bit in the current bitmask will be exclusive to only one of the single numbers, but the coolest is to use another bit manipulation to select the rightmost bit. To do this, we find the bitwise and of the bitmask and its negative representation, which is equivalent to ~(bitmask-1). There’s some complexity here, so let’s see it with the working example.

bitmask	-bitmask		bitmask & -bitmask
[0101]		[1011]			[0001]

Finally, we have distilled a single filter bit to differentiate the two single occurrence numbers. We apply it by iterating over the array of numbers again, only this time performing xor accumulation selectively by whether the current number has the bitmask bit set. In the same way as our original accumulation, numbers that occur an even number of times will zero out, and we’ll be left with the single number with the bit set on one side of the filter and the single number without the bit set on the other.

Input: [3,1,5,4,3,5]
bitmask filter: [0001]

number	binary_number		bitmask & binary_number ?	unique_xor_1	unique_xor_2
3	[0011]			true				[0011]		-
1	[0001]			true				[0010]		-
5	[0101]			true				[0111]		-
4	[0100]			false				-		[0100]
3	[0011]			true				[0100]		-
5	[0101]			true				[0001]		-

unique_xor_1: [0001] = 1
unique_xor_2: [0100] = 4

Excellent. And here’s the payoff from that hard work, a linear algorithm with constant space complexity.

vector<int> singleNumber(vector<int>& nums) {
   int bitmask = 0;
   // build bitmask of only bits which occur odd number of times,
   //  bitmask will equal the bit difference between the two single occurring numbers.
   for(auto num : nums) bitmask ^= num;
   // keep only the rightmost set bit in the bitmask, which will be unique to one of
   //  the singly occurring numbers.
   bitmask &= -bitmask;
   
   vector<int> singleNumbers(2);
   for(auto num : nums) {
	  // seperate the two single numbers by filtering with bitmask.
	  //  accumulated xor will be 0 for all duplicate numbers.
	  if(num & bitmask) {
		 singleNumbers[0] ^= num;
	  }
	  else {
		 singleNumbers[1] ^= num;
	  }
   }
   return singleNumbers;
}