More than 1 unique

#1

what we will do if we have more than 1 unique no., in that case it will do the exor of all unique number,so can we use hashing is it efficient also?

#2

Hashing is an option but there is still similar approach through xor.

Let x and y be the non-repeating elements we are looking for and arr[] be the input array. 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.

Let us see an example.
arr[] = {2, 4, 7, 9, 2, 4}

  1. Get the XOR of all the elements.
    xor = 2^4^7^9^2^4 = 14 (1110)
  2. Get a number which has only one set bit of the xor.
    Since we can easily get the rightmost set bit, let us use it.
    set_bit_no = xor & ~(xor-1) = (1110) & ~(1101) = 0010
    Now set_bit_no will have only set as rightmost set bit of xor.
  3. Now divide the elements in two sets and do xor of
    elements in each set and we get the non-repeating
    elements 7 and 9.
#3

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.