find the only unpaired element in the array

Question

Accenture interview question:

You have been given an array of size 2n+1 that have n pair of integers (can be +ve, -ve or 0) and one unpaired element.

How would you find the unpaired element?

Pair means duplicate. So (3,3) is a pair and (3,-3) is not a pair.

Answer 1

Take XOR of all the elements.

The pairs will cancel out as

a XOR a = 0 

and the result will be the only unpaired element as

0 XOR a = a 

If its okay to destroy the array you can XOR adjacent elements. Once done the last element of the array has the unpaired element:

N = Num of elements in array. for( i=1 to N )    arr[i] ^= arr[i-1];     print arr[N-1] 

If its not okay to destroy the array, you can make use of a variable to hold the result:

N = Num of elements in array. Unpaired = arr[0]; for( i=1 to N )    Unpaired = Unpaired ^ arr[i];     print Unpaired 

C function to do the same:

int findUnpaired(int *arr,int len) {  int i;                  // loop counter.  int unpaired;           // to hold the unpaired element.   unpaired = arr[0];      // initialize it with the 1st array ele.   for(i=1;i<len;i++) {    // loop for all remaining elements.     unpaired ^= arr[i];  // XOR each element with the running XOR.  }  return unpaired;        // return result. }