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

Question

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?

Answer 1

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

Answer 2

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;