Find integer not occurring twice in an array

Question

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. But I am looking for better solution that has time complexity of O(n).

Answer 1

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;
}