Find integer not occurring twice in an array

I am trying to solve this problem: In an integer array all numbers occur exactly twice, except for a single number which occurs exactly once.

A simple solution is to sort the array and then test for non repetition. Bu开发者_开发知识库t I am looking for better solution that has time complexity of O(n).

You can use "xor" operation on the entire array. Each pair of numbers will cancel each other, leaving you with the sought value.

int get_orphan(int const * a, int len)
{
    int value = 0;
    for (int i = 0; i < len; ++i)
        value ^= a[i];

    // `value` now contains the number that occurred odd number of times.
    // Retrieve its index in the array.
    for (int i = 0; i < len; ++i)
    {
        if (a[i] == value)
            return i;
    }

    return -1;
}