C++ program to find two unique numbers in an array

C++ program to find two unique numbers in an array: Here, we are going to learn how to find two unique numbers in a given array using bitwise operators?
Submitted by Bhanu Pratap Raghav, on December 24, 2018

Description:

Solution to find the two unique numbers from the set of numbers which occurred twice accept the unique numbers

Problem statement:

Write a C++ program that accepts input array from user and find the two unique number which occurred only once in array.

Example:

    Input: 
    10
    1 1 2 3 3 4 4 5 6 6		

    Output:
    2 5

Explanation:

This problem can be solved using the concept of Bitwise XOR, Bitwise AND, and bit masking.

Bitwise XOR:

Bitwise XOR ( ^ ) takes two equal-length bit patterns. If both bits in the compared position of the bit patterns are 0 or 1, the bit in the resulting bit pattern is 0, otherwise 1.

Example:

    A = 5 = 0101, B = 3 = 0011
    A ^ B = 0101 ^ 0011 = 0110 = 6

    Special Property of XOR: 
    A^A =0
    A^0 = A

Bitwise AND

Bitwise AND ( ^ ) takes two equal-length bit patterns. The output of bitwise AND is 1 if the corresponding bits of two operands is 1. If either bit of an operand is 0, the result of corresponding bit is evaluated to 0.

Example:

    A = 5 = 0101, B = 3 = 0011
    A & B = 0101 & 0011 = 0001 = 1

For the current problem:

First we take XOR of all elements of array.
Suppose we have: 1,1,2,3,3,4,4,5,6,6
On taking XOR of all elements, this will remove duplicates elements as A ^A =0
Then we get: 2^5 from above result
The result of 2^5 will definitely have at least a set bit, to find the rightmost set bit we do res&1 and make a count to take the record of current position. If we get a non-zero res&1 that's the position we want to get, break the loop, otherwise right shift the res and increment the count.
Make a mask using 1<<count, and take & one by one with all elements, Elements resulting a non zero result of mask &arr[i], take XOR of them .
Resulting XOR will result in firstNo.
Now for SecondNo, take XOR of firstNo with initial res. i.e., firstNo^ firstNo ^ secondNo.

Algorithm:

Set res=0 and find its XOR with all other elements of array.
Now res = firstNo ^ secondNo.
Get rightmost set bit position of res. using function findRightMostBit
Set bitPos = position of rightmost set bit.
Set a mask with a structure of set bit at position bitPos, using 1<<bitPos.
Set firstNo=0

For i=0 to size of array
    If mask & arr[i] != 0
        firstNo = firstNo ^ arr[i]
    //End of if
//End of loop

Set secondNo=firstNo ^ res.
Print firstNo and secondNo.

Program:

#include<bits/stdc++.h>
using namespace std;

int findRightMostBit(int x) {
	int i = 0;
	while (x > 0) {
		if(x&1){
			return i;
		}
		x>>1;
		i++;
	}
	return i;
}

void findUnique(int arr[], int size) {
	int res = 0;
	for (int i = 0; i < size; ++i) {
		res = res ^ arr[i];
	}
	
	int bitPos = findRightMostBit(res);
	int mask = (1 << bitPos);
	int firstNo=0;
	for (int i = 0; i < size; ++i)
	{
		if ((mask & arr[i]) != 0) {
			firstNo = firstNo ^ arr[i];
		}
	}	
	int secondNo = firstNo^ res;
	cout<<"Two Unique Numbers : "<<firstNo<<" , "<<secondNo;
}


int main() {
	int n;

	cout<<"Enter size of array : ";
	cin>>n;

	int arr[n];

	cout<<"Enter elements of array : \n";
	for (int i = 0; i < n; ++i)
	{
		cin>>arr[i];
	}

	findUnique(arr, n);

	return 0;
}

Output

Enter size of array : 10
Enter elements of array :
 1 1 2 3 3 4 4 5 6 6
Two Unique Numbers : 5 , 2