Q:

How to find the only number in an array that doesn't occur twice

The following is taken from a job interview: 

In a given array, which contains integers, each number repeats itself
  once except for one, which doesn't repeat. Write a function that finds
  the number that doesn't repeat.

I thought about using an HashSet, but it might complicate everything...
Any ideas of a simple solution?

A:

You can define an integer "result" initialized to 0, and then you do some bitwise operations by applying a XOR logic to all elements in your array.
At the end, "result" will be equal to the only element that appears only one time.
result = 0
for i in array:
  result ^= i
return result

http://en.wikipedia.org/wiki/Bitwise_operation#XOR
For instance, if your array contains the elements [3, 4, 5, 3, 4], the algorithm will return
3 ^ 4 ^ 5 ^ 3 ^ 4
But the XOR operator ^ is associative and commutative, so the result will be also equal to:
(3 ^ 3) ^ (4 ^ 4) ^ 5
Since i ^ i = 0 for any integer i, and i ^ 0 = i, you have
(3 ^ 3) ^ (4 ^ 4) ^ 5 = 0 ^ 0 ^ 5 = 5

A:

I've seen this question before. It's a trick. Assuming all the repeated numbers appear exactly twice you do this:
int result = 0;
for (int a : arr)
    result ^= a;

A:

Yet another "ordinary" solution (in Java):
public static int findSingle(int[] array) {

    Set<Integer> set = new HashSet<Integer>();

    for (int item : array) {
        if (!set.remove(item)) {
            set.add(item);
        }
    }       

    assert set.size() == 1;

    return set.iterator().next();
}

In my opinion the solution with XOR is kind of beautiful.
This one is not as fast as XOR but usage of HashSet makes it close to O(n). And it is certainly more readable.

