Problem

Given an integer array 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. You can return the answer in any order.

You must write an algorithm that runs in linear runtime complexity and uses only constant extra space.

Examples

Example 1:

Input:
nums = [1,2,1,3,2,5]
Output: [3,5]
Explanation: [5, 3] is also a valid answer.

Example 2:

Input: nums = [-1,0]
Output: [-1,0]

Example 3:

Input: nums = [0,1]
Output: [1,0]

Solution

This is very close to Single Number

Method 1 - Using Xor and Two Passes

Read about Explain x & (-x)

Algo

  • In the first pass, we XOR all elements in the array, and get the XOR of the two numbers we need to find. Note that since the two numbers are distinct, so there must be a set bit (that is, the bit with value ‘1’) in the XOR result. Find out an arbitrary set bit (for example, the rightmost set bit).

  • In the second pass, we divide all numbers into two groups, one with the aforementioned bit set, another with the aforementioned bit unset. Two different numbers we need to find must fall into thte two distrinct groups. XOR numbers in each group, we can find a number in either group.

Code

class Solution {

	public int[] singleNumber(int[] nums) {
		// Pass 1 : 
		// Get the XOR of the two numbers we need to find
		int diff = 0;

		for (int num: nums) {
			diff ^= num;
		}
		// Get its last set bit
		int rsb = diff & -diff; // right set bitMask for resultant

		// Pass 2 :
		int[] ans = { 0, 0 }; // this array stores the two numbers we will return
		for (int num: nums) {
			if ((num & rsb) == 0) { // the bit is not set
				ans[0] ^= num;
			} else { // the bit is set
				ans[1] ^= num;
			}
		}

		return ans;
	}
}

Dry Run

Suppose, the array is nums = [1, 2, 1, 3, 2, 5]. Our expected output should be [3, 5].

Now, lets look the binary representation:

1 = 001
2 = 010
1 = 001
3 = 011
2 = 010
5 = 101

In first step, we calculate xor of all elements. We know xor of same elements aka 1, 2 will lead to zero, so what we have diff as 3^5.

diff = 3 ^ 5 = 0b011 ^ 0b101 = 0b110 = 6

Now, when we look at 6 which is 0b110, there are 2 bits set. We know that a^b = 1 when a is 0, and b is 1 OR vice versa. So, a and b shouldn’t be same. We can use say the rightmost bit set. This will be done using:

rsb = diff & (-diff) = 0b110 & 0b010 = 0b010 = 2

So, we can use this rsb aka rightmost set bit to partition the numbers. We can start xoring the numbers based on this mask. We know one of the non repeating number will have 0 at this point, another will have 1 set. Rest of the duplicates will cancel out while xoring.

When rsb&num == 0 , then this is the set we get [1, 5], because:

1 & rsb = 0b001 & 0b010 = 0
5 & rsb = 0b101 & 0b010 = 0

So, we get ans[0] = 5 (as 1^1 cancels out).

When rsb&num != 0 , this is the set we get: [2, 3], because:

3 & rsb = 0b011 & 0b010 = 1
2 & rsb = 0b010 & 0b010 = 1

So, we get ans[1] = 3 (as 2^2 cancels out).