In this problem you are given an array of numbers. All repeating numbers are repeated even number of times.
All you need to do is to find 2 non repeating numbers in an array.

Sample Input:
6 23 27 23 17 17 37

Sample Output:
27
37

Why?Because in the given input array, 27 and 37 are the 2 numbers that occur once.

For more clarity of the question, watch part of the video.

Approach:

Moving On:

The problem here deals with finding two non-repeating elements in an input array where every other element repeats twice.

Here let's suppose we have non-repeating numbers as 'a' and 'b'.

Now if we use the XOR approach as we did in the problem All Repeating Except One, then we would get a ^ b, which would not be of any use, so we have to come up with a different approach.

Consider the following example:
Input: [36, 50, 24, 56, 36, 24, 42, 50]

Now let us try to take the XOR of the input array then we would get [ 0 1 0 0 1 0 ] which is a dead-end.

Now let us try to take the XOR of the non-repeating elements here that are 56 and 42, so 52 ^ 42 = [ 0 1 0 0 1 0 ] which is the same as the XOR of the entire input array.

This is since every other element in the input array except 42 and 56 are repeating twice hence they would cancel out each other. So we conclude that [ 0 1 0 0 1 0 ] is the XOR of both the entire array and also the XOR of non-repeating elements.

Now let us try to take the XOR of the input array then we would get [ 0 1 0 0 1 0 ] which is a dead-end.

Now let us try to take the XOR of the non-repeating elements here that are 56 and 42, so 52 ^ 42 = [ 0 1 0 0 1 0 ] which is the same as the XOR of the entire input array.

This is since every other element in the input array except 42 and 56 are repeating twice hence they would cancel out each other. So we conclude that [ 0 1 0 0 1 0 ] is the XOR of both the entire array and also the XOR of non-repeating elements.

For more clarity of the question, watch part of the video.

Now to solve this problem we will make use of the RSB mask (rightmost set bit mask). Yes, the same mask about which we have already discussed in one of the previous problems also.

If you haven't gone through it already then it is advised that you check out the video on RSB mask.

The RSB Mask of our XOR result for non-repeating elements would be [ 0 0 0 0 1 0 ].

This implies that at the 1st index there is a difference of bits in the non-repeating elements.

Now we wish to segregate the input array concerning whether the 1st index bit is set or not. After segregating we would get:

Set 1: [ 36, 24, 56, 36, 24 ] => 1st index bit set to 0
Set 2: [ 50, 42, 50 ] => 1st Index bit set to 1

Now if we observe that in both sets every element repeats itself twice except one and we were also able to separate both non-repeating elements in different sets.

This was possible since segregating at 1st index ensured that firstly both non-repeating would segregate and then in the entire array it ensured that only an odd number of elements would be present in any setting.

Now taking XOR in both sets would yield us the non-repeating elements as the problem has now been reduced to the previous problem, in which we find one unique element in an array with the rest elements repeating.

For more clarity of the question, watch part of the video.

Let's try to code this!

public static void solution(int[] arr){
//initializing a variable xor to 0.
int xor = 0;
//for loop to operate XOR operation among all elements of the array
for(int i = 0 ; i < arr.length; i++){
xor ^= arr[i];
}
//rightmost bit mask of the xor of all the elements of the array
//(also the rightmost bit mask of the two unique numbers)
int rsb = xor & ~(xor - 1);
//initializing a variable x
int x = 0;
//initializing a variable y
int y = 0;
//for loop on the length of the array
for(int i = 0 ; i < arr.length; i++){
//checking if the '&' of ith element of the array and rightmost bit mask is
//zero or not
if((arr[i] & rsb) == 0){
//if it is zero than we include it with the result of rest of the elements
//with the same condition therefore segregating all such elements into set 1
x ^= arr[i];
}
//elst we include it with the result of set 2
else{
y ^= arr[i];
}
}
//doing above step we get the 2 unique values in x and y
//then to print the number in increasing order we check is x < y
if(x < y){
//if x is smaller, then we first print x and then y
System.out.println(x);
System.out.println(y);
//if not, then we first print y and then x
}else{
System.out.println(y);
System.out.println(x);
}
}

java;
true";

For more clarity of the question, watch part of the video.

import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args){
Scanner scn = new Scanner(System.in);
int n = scn.nextInt();
int[] arr = new int[n];
for(int i = 0 ; i < n; i++){
arr[i] = scn.nextInt();
}
solution(arr);
}
public static void solution(int[] arr){
int xor = 0;
for(int i = 0 ; i < arr.length; i++){
xor ^= arr[i];
}
int rsb = xor & ~(xor - 1);
int x = 0;
int y = 0;
for(int i = 0 ; i < arr.length; i++){
if((arr[i] & rsb) == 0){
x ^= arr[i];
}else{
y ^= arr[i];
}
}
if(x < y){
System.out.println(x);
System.out.println(y);
}else{
System.out.println(y);
System.out.println(x);
}
}
}

java;
true";

Analysis

Time Complexity:O(n)

The time complexity for the function is linear as we are traversing on every element of the array.

Space complexity:O(1)

The space complexity for the function is constant.

We hope that this article was helpful. If somehow you are finding it difficult to understand this problem then we advise you to watch our video lecture of this problem.

Trust me it will just get easier to understand after you have watched the solution video.

You can contact us via our website. Doubts, suggestions and feedback are always welcomed.

It is also advised that you follow the sequence of modules and questions which is there on our website.

Keep practicing more and more problems daily. Meditate enough on each step of each problem.