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.
Non Repeating Numbers using Sorting:
First, sort all the elements. In the sorted array, by comparing adjacent elements we can easily get the non-repeating elements.
Below is the implementation of the above approach:
// C++ program for above approach
#include <bits/stdc++.h>
using namespace std;
/* This function sets the values of
*x and *y to non-repeating elements
in an array arr[] of size n*/
vector<int> get2NonRepeatingNos(int nums[], int n)
{
sort(nums, nums + n);
vector<int> ans;
for (int i = 0; i < n - 1; i = i + 2) {
if (nums[i] != nums[i + 1]) {
ans.push_back(nums[i]);
if(ans.size()==2)
return ans;
i = i - 1;
}
}
ans.push_back(nums[n - 1]);
return ans;
}
/* Driver code */
int main()
{
int arr[] = { 2, 3, 7, 9, 11, 2, 3, 11 };
int n = sizeof(arr) / sizeof(*arr);
vector<int> ans = get2NonRepeatingNos(arr, n);
cout << "The non-repeating elements are " << ans[0]
<< " and " << ans[1];
}
// This code is contributed by rathbhupendra
// Java program for above approach
import java.util.*;
public class Solution
{
/* This function sets the values of
*x and *y to non-repeating elements
in an array arr[] of size n*/
static ArrayList<Integer> get2NonRepeatingNos(int nums[], int n)
{
Arrays.sort(nums);
ArrayList<Integer> ans = new ArrayList<>();
for (int i = 0; i < n - 1; i = i + 2) {
if (nums[i] != nums[i + 1]) {
ans.add(nums[i]);
i = i - 1;
}
}
if (ans.size() == 1)
ans.add(nums[n - 1]);
return ans;
}
/* Driver code */
public static void main(String[] args) {
int arr[] = { 2, 3, 7, 9, 11, 2, 3, 11 };
int n = arr.length;
ArrayList<Integer> ans = get2NonRepeatingNos(arr, n);
System.out.print("The non-repeating elements are ");
System.out.println(ans.get(0) + " and " + ans.get(1));
}
}
// This code is contributed by karandeep1234.
# python program for above approach
# function sets the values of
# x and *y to non-repeating elements
# in an array arr[] of size n
def get2NonRepeatingNos(nums, n):
nums.sort();
ans=[];
i=0;
while(i<n-1):
if (nums[i] != nums[i + 1]):
ans.append(nums[i])
i = i + 1
else:
i=i+2;
if (len(arr) == 1):
ans.append(nums[n - 1]);
return ans;
# Driver code
arr = [ 2, 3, 7, 9, 11, 2, 3, 11 ];
n = len(arr);
ans = get2NonRepeatingNos(arr, n);
print("The non-repeating elements are ", ans[0], " and ", ans[1]);
// C# program for above approach
using System;
using System.Collections;
using System.Collections.Generic;
public class GFG {
/* This function sets the values of
*x and *y to non-repeating elements
in an array arr[] of size n*/
static ArrayList get2NonRepeatingNos(int[] nums, int n)
{
Array.Sort(nums);
ArrayList ans = new ArrayList();
for (int i = 0; i < n - 1; i = i + 2) {
if (nums[i] != nums[i + 1]) {
ans.Add(nums[i]);
i = i - 1;
}
}
if (ans.Count == 1)
ans.Add(nums[n - 1]);
return ans;
}
static public void Main()
{
// Code
int[] arr = { 2, 3, 7, 9, 11, 2, 3, 11 };
int n = arr.Length;
ArrayList ans = get2NonRepeatingNos(arr, n);
Console.Write("The non-repeating elements are ");
Console.WriteLine(ans[0] + " and " + ans[1]);
}
}
// This code is contributed by lokesh.
// JavaScript program for above approach
/* This function sets the values of
*x and *y to non-repeating elements
in an array arr[] of size n */
function get2NonRepeatingNos(nums, n){
nums.sort();
var ans = [];
for (let i = 0; i < n - 1; i = i + 2) {
if (nums[i] != nums[i + 1]) {
ans.push(nums[i]);
i = i - 1;
}
}
if (ans.length == 1)
ans.push(nums[n - 1]);
return ans;
}
var arr = [ 2, 3, 7, 9, 11, 2, 3, 11 ];
var n = arr.length;
var ans = get2NonRepeatingNos(arr, n);
console.log("The non-repeating elements are " + ans[0] + " and " + ans[1]);
// This code is contributed by lokeshmvs21.
Output
The non-repeating elements are 7 and 9
Time complexity: O(n log n)
Auxiliary Space: O(1)
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 :