Accenture interview question - Find the only unpaired element in the array

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.
}

Answer 2

A simpler method would be to add all the numbers. While adding change the sign of the one of the numbers in the pair, so that the pair sum becomes 0.

O(n) time and O(1) space.

Answer 3

Here'a a simple linq solution that can easily be extended to provide the number of occurrences of each unique element:

     int[] numbers = { -1, 0, 1, 2, 3, 4, 5, 4, 3, 2, 1 };

     var numberGroups =
         from n in numbers
         group n by n into g
         select new { Number = g.Key, IsPaired = g.Count() == 2 };

     Console.WriteLine("Unpaired elements:");
     foreach (var group in numberGroups)
     {
        if (!group.IsPaired)
           Console.WriteLine(group.Number);
     }

Output:

Unpaired elements: -1 0 5

Answer 4

Alternate solution, to find all unique values in O(n) and O(n) space:

Initialize a Hash table.
For each value in the array, check if the value exists in the Hash table, if it does, remove it, if it doesn't, add it.
Return value is all the items inside the Hash table.

Can easily be modified to use a dictionary if the recurring values can recur more than once.

Answer 5

Take the sum of all the elements.