DEV Community

loading...

Find non-repeating element from repeating array

prateekbud profile image Prateek budhiraja ・3 min read

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
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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;
 }
Enter fullscreen mode Exit fullscreen mode

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
We have the answer now
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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);
}
Enter fullscreen mode Exit fullscreen mode

Mission accomplish!

Discussion (0)

pic
Editor guide