Last Updated: 7 Dec, 2020
Find Non - Repeating Numbers
Easy
Asked in companies
You are given an array of integers ‘A’ having ‘N’ number of elements. It is given that all the numbers in the array occur twice except the two numbers that appear only one time. You need to find those two non-repeating numbers.
For Example:
If the given array is [ 4, 7, 3, 2, 7, 2 ], you have to find ‘4’ and ‘3’ as 4 and 3 occur one time, and the rest of the elements ( 7 and 2 ) are occurring twice.
Input Format:
The first line contains a single integer T representing the number of test cases.
The first line of each test case contains a single integer ‘N’, denoting the number of elements in the array.
The second line of each test case contains ‘N’ space-separated integers denoting the elements of the given array.
Output Format:
For each test case, print two space-separated integers that denote the two non-repeating numbers in the given array.
Print the output of each test case in a new line.
Note:
You do not need to print anything. It has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 10
4 <= N <= 10^5
1 <= A[i] <= 10^5
Time Limit: 1 sec
Approaches
The simple idea is to sort the elements and compare every element with its adjacent elements. If any element A[i] is neither equal to its left nor to its right element, A[i] is a non-repeating element.
Algorithm
- Sort the elements of the given array using any sorting algorithm.
- Initialize an array ‘res’ to store the non-repeating elements.
- If any element A[i] is not equal to its left and right adjacent element, add A[i] to ‘res’.
- Return ‘res’
We will use a bitwise XOR operation to solve this problem. We will store the XOR of all the elements in a variable ‘temp’.
Bitwise XOR of two same numbers is always 0. For eg 3 = 011. So 3 XOR 3 is (011) XOR (011) i.e 0. So the bitwise XOR of all elements will be because of the two non-repeating numbers.
Now the question is how to find the two non-repeating numbers from this XOR result?
For that, we have to find the rightmost set bit in ‘temp’. Let it be at ‘p’ position.
XOR of all elements of the array having p-th bit as set(1) will give one non-repeating number and similarly XOR of all elements having p-th bit 0 will give the second non-repeating number.
Algorithm
- Store XOR of all numbers in a variable ‘temp’.
- Find the rightmost set bit in ‘temp’ and store it in a variable ‘setBit’.
- Initialize two variables, ‘x’ and ‘y’, to store the non-repeating numbers.
- Traverse the given array using a variable ‘i’
- If bitwise AND of A[i] and ‘setBit’ is greater than 0.
- Store bitwise XOR of ‘x’ and A[i] in ‘x’.
- Else
- Store bitwise XOR of ‘y’ and A[i] in ‘y’.
- If bitwise AND of A[i] and ‘setBit’ is greater than 0.
- Initialize an array ‘res’ to store the non-repeating numbers.
- Add ‘x’ and ‘y’ to ‘res’
- Return ‘res’