## DEV Community is a community of 616,766 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

# Find non-repeating element from repeating array

Q1. If we have an array where all the elements are repeating twice and only one element is not repeating.

``````{2, 4, 7, 1, 2, 4, 1}
It should return 7
``````

There are many ways to solve this, but we will do it with bit manipulation.

In bit manipulation, there is a concept called XOR(^), it can on the bit when the bits are different and off bits if they are same.

``````0 ^ 0 -> 0
0 ^ 1 -> 1
1 ^ 0 -> 1
1 ^ 1 -> 0
``````

Which means if we XOR a number with itself it will cancel out and results in 0 (a^a -> 0).
We can use this property to cancel out the repeating numbers.

We will iterate through the array and XOR all the elements of the array, all the repeating elements in the array will cancel themselves and only the number which is not repeating will left.

``````public int nonRepeating(int[] arr){
int res=0;
for(int val: arr){
res^=val;
}
return res;
}
``````

Q2. What if we have an array of repeating integers and now two elements are not repeating?
Step 1: We will find the XOR like we did in the last example.
Now we will have an value which is the XOR of two numbers, non repeating two numbers to be exact.
Step 2: We have to find one number from that two numbers by distinguishing between two numbers.
Step 3: XOR one number from the result and we can get the second number as well.

``````Input: {2, 4, 7, 9, 2, 4}
Step 1: res = 7^9
Step 2: Find 7 somehow
Step 3: 7^7^9 = 9
``````

But the main question is how are we planning to find 7?

1. Find the first occurrence of 1 from the the right most (LSB) and make a number where there is 1 on that position. {which means one of the number's bit on this position is 0 and others is 1, as XOR gives 1 only when bits are different.}
2. & that number with all the elements of the array.
3. If the result of & is greater than 0, it means the 1 is present in that value as well. Result of this will be one of the number present in result.

Worst said than done, Let's see the example

``````Input: {2, 4, 7, 9, 2, 4}
Result: 7^9  -> 0111 ^ 1001 -> 1110 {first occurrence is at 1st position}
temp -> 0010  {1 at 1st position}
& temp with all values in array
{ this will results in >0 if the number has 1 in 1st position }
{ in this step we are dividing array in two parts, one part
contains the numbers which has 1 in in their 1st position and
second part where they don't have 1 in there 1st position }

After this if the result is >0, we will XOR all the numbers in this group with result(7^9) and that will give us 9.
How?
2 -> 0010 ^ 0010 -> 2>0  { XOR with res -> 7^9^2 }
4 -> 0100 ^ 0010 -> 0!>0 {skip}
7 -> 0111 ^ 0010 -> 2>0 { XOR with res -> 7^9^2^7 -> 9^2}
9 -> 1001 ^ 0010 -> 0!>0 {skip}
2 -> 0010 ^ 0010 -> 2>0 { XOR with res -> 9^2^2 -> 9}
4 -> 0100 ^ 0010 -> 0!>0 {skip}

Hence we get out result 9
``````

Now when we get 9, we can simply get 7 by XORing result with 9.

``````public void getNonRepeating(int[] arr){
int res=0;
for(int val:arr){
res^=val;
}
int temp=res&-res; //to get first set bit {2nd compliment}
int first=res;
for(int val:arr){
if((temp&val)>0)
first^=val;
}
int second=res^first;
System.out.println(first+"  "+second);
}
``````

Mission accomplish!