Find an integer not repeating twice in an array

Question

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

A simple solution is to sort the array and then check for duplication. But I am looking for the best solution having O (n) time complexity.

Answer 1

You can use the "xor" operation for the whole array. Each pair of numbers will cancel each other, leaving you with the desired 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; }