Problem
Given an array in which all numbers except two are repeated once. (i.e. we have 2n+2 numbers and n numbers are occurring twice and remaining two have occurred once). Find those two numbers in the most efficient way.
Example
Input : {2,4,7,9,2,4}
Output : 7,9
Solution
Method 1 - Use Sorting
First sort all the elements. In the sorted array, by comparing adjacent elements we can easily get the non-repeating elements. Time complexity of this method is O(nLogn)
Method 2 - Use XOR
Let x and y be the non-repeating elements we are looking for and arr[] be the input array. First calculate the XOR of all the array elements.
xor = arr\[0\]^arr\[1\]^arr\[2\].....arr\[n-1\]
```All the bits that are set in xor will be set in one non-repeating element (x or y) and not in other. So if we take any set bit of xor and divide the elements of the array in two sets – one set of elements with same bit set and other set with same bit not set. By doing so, we will get x in one set and y in another set. Now if we do XOR of all the elements in first set, we will get first non-repeating element, and by doing same in other set we will get the second non-repeating element.
Let us see an example.
arr[] = {2, 4, 7, 9, 2, 4}
- Get the XOR of all the elements.
xor = 2^4^7^9^2^4 = 14 (1110) - Get a number which has only one set bit of the xor.
Since we can easily get the rightmost set bit, let us use it.
set_bit_no = xor & ~(xor-1) = (1110) & ~(1101) = 0010
Now set_bit_no will have only set as rightmost set bit of xor. - Now divide the elements in two sets and do xor of
elements in each set, and we get the non-repeating
elements 7 and 9. Please see implementation for this
step.
**Implementation:**
class Pair{
public int x;
public int y;
}
// This finction sets the values of *x and *y to nonr-epeating
// elements in an array arr[] of size n
public Pair get2NonRepeatingNos(int arr[], int n)
{
int xor = arr[0]; // Will hold xor of all elements
int set_bit_no; // Will have only single set bit of xor
int i;
int x = 0;
int y = 0;
// Get the xor of all elements
for(i = 1; i < n; i++)
xor ^= arr[i];
// Get the rightmost set bit in set_bit_no
set_bit_no = xor & ~(xor-1);
// Now divide elements in two sets by comparing rightmost set
bit of xor with bit at same position in each element.
for(i = 0; i < n; i++)
{
if(arr[i] & set_bit_no)
x = x ^ arr[i]; //XOR of first set
else
y = y ^ arr[i]; //XOR of second set
}
return new Pair(x,y);
}
**Time Complexity:** O(n)
**Auxiliary Space:** O(1)
**References**
[http://www.geeksforgeeks.org/find-two-non-repeating-elements-in-an-array-of-repeating-elements/](http://www.geeksforgeeks.org/find-two-non-repeating-elements-in-an-array-of-repeating-elements/)