Q:

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

mahmoud2506
Save to bookmark
|
2022-05-05
|
  102 
0

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:

  1. First we take XOR of all elements of array.
  2. Suppose we have: 1,1,2,3,3,4,4,5,6,6
  3. On taking XOR of all elements, this will remove duplicates elements as A ^A =0
    Then we get: 2^5 from above result
  4. 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.
  5. 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 .
  6. Resulting XOR will result in firstNo.
  7. Now for SecondNo, take XOR of firstNo with initial res. i.e., firstNo^ firstNo ^ secondNo.
  8.  
C++ programming, exam questions, C++ programming exam-questions,
login and add your own answer to this question

All Answers

mahmoud2506
2022-05-05
need an explanation for this answer? contact us directly to get an explanation for this answer

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

need an explanation for this answer? contact us directly to get an explanation for this answer

total answers (1)

Similar questions

need a help?

find thousands of online teachers now