Number which occurs only once in the array [duplicate]

Question

Possible Duplicate:
Finding a single number in a list

Given an array of numbers, except for one number all the others, occur twice. What should be the algorithm to find that number which occurs only once in the array?

Example

a[1..n] = [1,2,3,4,3,1,2] 

should return 4

Answer 1

Let the number which occurs only once in the array be x

x <- a[1]
for i <- 2 to n
   x <- x ^ a[i]
return x

Since a ^ a = 0 and a ^ 0 = a

Numbers which occur in pair cancel out and the result gets stored in x

Working code in C++

#include <iostream>

template<typename T, size_t N>
size_t size(T(&a)[N])
{
    return N;
}
int main()
{
   int a [] = {1,2,3,4,3,1,2};
   int x = a[0];
   for (size_t i = 1; i< size(a) ; ++i)
   {
      x = x ^ a[i];
   }
   std::cout << x;
} 

Answer 2

1. Create new int i = 0
2. XOR each item with i
3. After all iterations there will be expected number in i