Fastest way to find an unique elements out of given numbers

I have n numbers. n <= 1000000. Each number will be positive integer and less than 10^9.

It is sure that there will be only one number will occur once, rest will occur twice or even number of times.

The shortest solution I know is the result of XOR of all numbers. I want to know

• What will be 开发者_StackOverflow中文版the complexity of the standard XOR solution.
• How can we optimize the solution.

---

XORing all the numbers will be of O(n) complexity, since you'll need to visit each element only once.

I can't think of any way to optimize this further, given your requirements. XOR is a very cheap operation, and the nature of the problem requires you to visit each element at least once: otherwise, you cannot possibly know which value is unique.

---

The XOR algorithm is the right algorithm and the fastest one. The slow part is the way that you are reading the input.

For instance, scanf in C is slower than handrolling your own number algorithm with getchar (or even better getchar_unlocked). On the SPOJ problem that you mentioned, I got an improvement from 1.35s to 0.14s just by making this change. I'm sure that the remaining 0.04 to get the best time on the site is just due to better low-level IO than my code.

---

You can go for hashing. A raw solution would be to use the unique number as a key to your hash table. If that is possible, then you can probably use the hashing algorithm. A simple example is to use the numbers as an index in an array. Now, the space will be too much (I mean too too much), but can be optimized further.