Using the XOR operator to find duplicate elements in an array is not in many cases

Question

I came across a message How do I find a duplicate element in an array of shuffled consecutive integers? , but later realized that this fails for many inputs.

For example:
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 change this code so that the duplicate element can be found for all cases?

Answer 1

From the original question:

Suppose you have an array of 1001 integers. Integers are in random order, but you know that each of the integers is from 1 to 1000 (inclusive). In addition, each number appears only once in the array, with the exception of one number that occurs twice.

Basically, he says that the algorithm only works when you have consecutive integers, starting from 1 , ending with some N.

If you want to change it in a more general case, you need to do the following:

Find the minimum and maximum value in the array. Then calculate the expected result (xor all integers between the minimum and maximum). Then calculate the xor of all the elements in the array. Then xor are two things and you will get the result.

Answer 2

The XOR operator has the property that 'a' XOR 'a' will always be 0, that is, they are canceled, so if you know that your list has only one duplicate and that the range says x to y, 601 - 607 in your case It is possible to store the xor of all elements from x to y in a variable, and then xor this variable with all the elements that you have in your array. Since there will be only one element that will be duplicated, it will not be undone due to the xor operation, and that will be your answer.

 void main() { int a[8]={601,602,603,604,605,605,606,607}; int k,i,j=601; for(i=602;i<=607;i++) { j=j^i; } for(k=0;k<8;k++) { j=j^a[k]; } printf("%d",j); } 

This code will return 605 as desired!

Answer 3

Here is the code shown in the original question, which is different from your implementation. You changed it to use a local variable instead of the last member of the array, which matters:

 for (int i = 1; i < 1001; i++) { array[i] = array[i] ^ array[i-1] ^ i; } printf("Answer : %d\n", array[1000]); 

Answer 4

 //There i have created the program to find out the duplicate element in array. Please edit if there are required some changes. int main() { int arr[] = {601,602,603,604,605,605,606,607}; //int arr[] = {601,601,604,602,605,606,607}; int n= sizeof(arr)/sizeof(arr[0]); for (int i = 0; i < n; i++) { for (int j = i+1; j < n; j++) { int res = arr[i] ^ arr[j]; if (res == 0) { std::cout<< "Repeated Element in array = "<<arr[i]<<std::endl; } } } return 0; } 

// OR You can use HashTable and Hash Function when you enter the same file value in a hash table so that the time you can do if it is more than one value at a specific HashTable index, then you can say that there is a duplicate value in the array.