Non Repeating Numbers using XOR
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 others. 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 another 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 the first set, we will get the first non-repeating element, and by doing same in other sets we will get the second non-repeating element.
Illustration:
We have the array: [2, 4, 7, 9, 2, 4]
- XOR = 2 ^ 4 ^ 7 ^ 9 ^ 2 ^ 4 = 2 ^ 2 ^ 4 ^ 4 ^ 7 ^ 9 = 0 ^ 0 ^ 7 ^ 9 = 7 ^ 9 = 14
- The rightmost set bit in binary representation of 14 is at position 1 (from the right).
- Divide the elements into two groups based on the rightmost set bit.
- Group 1 (rightmost bit set at position 1): [2, 7, 2]
- Group 2 (rightmost bit not set at position 1): [4, 9, 4]
- XOR all elements in Group 1 to find one non-repeating element.
- Non-repeating element 1 = 2 ^ 7 ^ 2 = 7
- XOR all elements in Group 2 to find the other non-repeating element.
- Non-repeating element 2 = 4 ^ 9 ^ 4 = 9
- The two non-repeating elements are 7 and 9,
Below is the implementation of the above approach:
// C++ program for above approach
#include <bits/stdc++.h>
using namespace std;
vector<int> get2NonRepeatingNos(vector<int>& nums)
{
// Pass 1:
// Get the XOR of the two numbers we need to find
long long int diff = 0;
for (auto i : nums) {
diff = i ^ diff;
}
// Get its last set bit
diff &= -diff;
// Pass 2:
vector<int> rets = {
0, 0
}; // this vector stores the two numbers we will return
for (int num : nums) {
if ((num & diff) == 0) { // the bit is not set
rets[0] ^= num;
}
else { // the bit is set
rets[1] ^= num;
}
}
// Ensure the order of the returned numbers is
// consistent
if (rets[0] > rets[1]) {
swap(rets[0], rets[1]);
}
return rets;
}
// Driver code
int main()
{
vector<int> arr = { 2, 3, 7, 9, 11, 2, 3, 11 };
vector<int> result = get2NonRepeatingNos(arr);
cout << "The non-repeating elements are " << result[0]
<< " and " << result[1];
}
import java.util.*;
public class Main {
// Function to find two non-repeating numbers in an array
public static int[] get2NonRepeatingNos(int[] nums) {
// Pass 1:
// Get the XOR of the two numbers we need to find
int diff = 0;
for (int num : nums) {
diff ^= num;
}
// Get its last set bit
diff &= -diff;
// Pass 2:
int[] rets = new int[2]; // this array stores the two numbers we will return
Arrays.fill(rets, 0);
for (int num : nums) {
if ((num & diff) == 0) { // the bit is not set
rets[0] ^= num;
} else { // the bit is set
rets[1] ^= num;
}
}
// Ensure the order of the returned numbers is consistent
if (rets[0] > rets[1]) {
int temp = rets[0];
rets[0] = rets[1];
rets[1] = temp;
}
return rets;
}
// Driver code
public static void main(String[] args) {
int[] arr = {2, 3, 7, 9, 11, 2, 3, 11};
int[] result = get2NonRepeatingNos(arr);
System.out.println("The non-repeating elements are " + result[0] + " and " + result[1]);
}
}
# Function to find two non-repeating numbers in an array
def get_2_non_repeating_nos(nums):
# Pass 1:
# Get the XOR of the two numbers we need to find
diff = 0
for num in nums:
diff ^= num
# Get its last set bit
diff &= -diff
# Pass 2:
rets = [0, 0] # this list stores the two numbers we will return
for num in nums:
if (num & diff) == 0: # the bit is not set
rets[0] ^= num
else: # the bit is set
rets[1] ^= num
# Ensure the order of the returned numbers is consistent
if rets[0] > rets[1]:
rets[0], rets[1] = rets[1], rets[0]
return rets
# Driver code
arr = [2, 3, 7, 9, 11, 2, 3, 11]
result = get_2_non_repeating_nos(arr)
print("The non-repeating elements are", result[0], "and", result[1])
// Function to find two non-repeating numbers in an array
function get2NonRepeatingNos(nums) {
// Pass 1:
// Get the XOR of the two numbers we need to find
let diff = 0;
for (let i of nums) {
diff = i ^ diff;
}
// Get its last set bit
diff &= -diff;
// Pass 2:
let rets = [0, 0]; // this array stores the two numbers we will return
for (let num of nums) {
if ((num & diff) === 0) { // the bit is not set
rets[0] ^= num;
} else { // the bit is set
rets[1] ^= num;
}
}
// Ensure the order of the returned numbers is consistent
if (rets[0] > rets[1]) {
[rets[0], rets[1]] = [rets[1], rets[0]];
}
return rets;
}
// Driver code
let arr = [2, 3, 7, 9, 11, 2, 3, 11];
let result = get2NonRepeatingNos(arr);
console.log("The non-repeating elements are " + result[0] + " and " + result[1]);
Output
The non-repeating elements are 7 and 9
Time Complexity: O(n)
Auxiliary Space: O(1)
Please refer below post for detailed explanation :
Find the two non-repeating elements in an array of repeating elements/ Unique Numbers 2
Given an array arr[] containing 2*N+2 positive numbers, out of which 2*N numbers exist in pairs whereas the other two number occur exactly once and are distinct. Find the other two numbers. Return in increasing order.
Example:
Input: N = 2, arr[] = {1, 2, 3, 2, 1, 4}
Output:3 4
Explanation: 3 and 4 occur exactly once.Input: N = 1, arr[] = {2, 1, 3, 2}
Output: 1 3
Explanation: 1 3 occur exactly once.