How to find two non-repeating numbers in an array

Problem Statement

We have 2*N +2 numbers. In this expression, every number comes twice except two numbers which occur once.

Find these two numbers.

Pre-Requisites

• XOR and its properties.

Problem Explanation

Let two numbers that occur once be a and b. The array be a list of 2*N+2 numbers.

1. N=2, array = [2, 1, 3, 5, 1, 3]

   • In this example, {1, 3} occur twice and {2, 5} occur once.

   • Thus, a = 2 and b = 5

2. N =3, array = [1, 10, 10, 1, 5, 6, 5, 9]

   • a = 6

   • b = 9

Solution

Let a and b be the two unique numbers.

We’ll first calculate the res and cumulative XOR of the array.

We know that the XOR of any number occurring even times is 0. Moreover, every number except a and b occur twice.

Thus, effectively res = a^b.

Now, a fundamental observation is:

• We know, res = a ^ b.

Note: If the ith bit of res is set, the ith bit of a and the ith bit of b must be different.

We’ll split the main array into two arrays (array1 and array2).

• array1 = List of numbers of array which have their ith bit same as ith bit of a.

• array2 = List of numbers of array which have their ith bit same as ith bit of b.

The cumulative XOR of array1 will give us the value of a, and the cumulative XOR of array2 will provide us with the value of b.

Explanation

• Line 1: We take N as input.

• Line 2: We take 2*N+2 numbers as input and store them in an array.

• Lines 3–4: We initialize two unique numbers (a,b) and cumulative XOR of array and res to 0.

• Line 6: We loop over every value v of the array to calculate res.

• Line 9: We initialize lsb (the least significant bit) to 0.

• Lines 10–12: We start the while loop to calculate lsb of res.

• Lines 15–17: We loop over every value v of the array.

  • Line 16: If the lsbth bit of v is set, then we perform a = a^v, since we want a to be the cumulative XOR of all numbers in array with their lsb bit set.

  • Line 17: If the lsbth bit of v is off, then b = b^v.

• Line 19: Consequently, the first unique number will be a, and the second unique number will be b.