Using XOR operator for finding duplicate elements in a array fails in many cases

Question

I came across a post How to find a duplicate element in an array of shuffled consecutive integers? but later realized that this fails for many input.

For ex:
arr[] = {601,602,603,604,605,605,606,607}

#include <stdio.h>
int main()
{
int arr[] = {2,3,4,5,5,7};
int i, dupe = 0;
for (i = 0; i < 6; i++) {
    dupe = dupe ^ a[i] ^ i;
}
printf ("%d\n", dupe);
return 0;
}

How can I modify this code so that the duplicate element can be found for all the cases ?

Answer 1

Remember these two properties of XOR operator :

(1) If you take xor of a number with 0 ( zero ) , it would return the same number again.

Means , n ^ 0 = n

(2) If you take xor of a number with itself , it would return 0 ( zero ).

Means , n ^ n = 0

Now , Coming to the problem :

   Let    Input_arr = { 23 , 21 , 24 , 27 , 22 , 27 , 26 , 25 }    

   Output should be 27 ( because 27 is the duplicate element in the Input_arr ).

Solution :

Step 1 : Find “min” and “max” value in the given array. It will take O(n).

Step 2 : Find XOR of all integers from range “min” to “max” ( inclusive ).

Step 3 : Find XOR of all elements of the given array.

Step 4 : XOR of Step 2 and Step 3 will give the required duplicate number.

Description :

Step1 : min = 21 , max = 27

Step 2 : Step2_result = 21 ^ 22 ^ 23 ^ 24 ^ 25 ^ 26 ^ 27 = 20

Step 3 : Step3_result = 23 ^ 21 ^ 24 ^ 27 ^ 22 ^ 27 ^ 26 ^ 25 = 15

Step 4 : Final_Result = Step2_result ^ Step3_result = 20 ^ 15 = 27

But , How Final_Result calculated the duplicate number ?

Final_Result = ( 21 ^ 22 ^ 23 ^ 24 ^ 25 ^ 26 ^ 27 ) ^ ( 23 ^ 21 ^ 24 ^ 27 ^ 22 ^ 27 ^ 26 ^ 25 )

Now , Remember above two properties : n ^ n = 0 AND n ^ 0 = n

So , here ,

Final_Result = ( 21 ^ 21 ) ^ ( 22 ^ 22 ) ^ ( 23 ^ 23 ) ^ ( 24 ^ 24 ) ^ ( 25 ^ 25 ) ^ ( 26 ^ 26 ) ^ ( 27 ^ 27 ^ 27 )

             = 0 ^ 0 ^ 0 ^ 0 ^ 0 ^ 0 ^ ( 27 ^ 0 ) ( property applied )

             = 0 ^ 27 ( because we know 0 ^ 0 = 0 )

             = 27 ( Required Result )