find the only unpaired element in the array

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

Solution 2:

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.

Solution 3:

Single line Linq example with a XOR solution :

Demo on DotNetFiddle

public static void Main()
{
    int[] tab = { 1, 2, 3, 2, 1 };
    Console.WriteLine(GetSingle(tab));
}

private static int GetSingle(IEnumerable<int> tab)
{
    return tab.Aggregate(0, (current, i) => current ^ i);
}

For fun and profit

Edit:

Explication for this snippet.

var a = 2;
var b = 2;
Console.WriteLine(a ^ b); // will print 0
// because x ^ x == 0

var c = 3;
Console.WriteLine(a ^ b ^ c); // will print 3
// because 0 ^ x == x

Console.WriteLine(0 ^ a); // guess the output
// get it? :)
// Now, lets aggregate this enumerable ;)

Solution 4:

The best answer is the XOR operator. Just for fun another way is, if you are allowed to sort the array, to sort it and compare adjacent integers. This assumes all integers appear exactly twice with one integer appearing once.

// Random array of integers
int[] arr = {1, 2, 3, 4, 5, 6, 7, 9, 1, 2, 3, 4, 5, 6, 7, 8, 9};

// Sort the array.
Arrays.sort(arr);

// Array now looks like: 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 9 9 
// Cycle through array comparing adjacent values.
for(int i = 0; i < arr.length; i++){

    // This would mean the single number was the last element in the array.
    if(i == arr.length-1)
        singleNum = arr[i];

    // If the adjacent elements are the same, skip foward. 
    if(i < arr.length-1 && arr[i] == arr[i+1])
        i ++;
    else
        // Otherwise, you found the single number.
        singleNum = arr[i];
}