</>EmbeddedInterview

How do you find the single number that appears once when all others appear twice?

EasyBit Manipulation

Short answer: XOR all the elements together. Every number that appears twice cancels itself (a ^ a = 0), and 0 ^ x = x, so only the unique value remains. O(n) time, O(1) memory.

#include <stddef.h>

int find_unique(const int *arr, size_t n)
{
    int result = 0;
    for (size_t i = 0; i < n; i++)
        result ^= arr[i];
    return result;
}
/* {4, 1, 2, 1, 2} -> 4 */

Why order does not matter: XOR is commutative and associative, so 4 ^ 1 ^ 2 ^ 1 ^ 2 can be regrouped as 4 ^ (1 ^ 1) ^ (2 ^ 2) = 4 ^ 0 ^ 0 = 4.

Comparison with other approaches

Approach Time Extra memory
Two nested loops O(n²) O(1)
Sort, then scan pairs O(n log n) O(1) or O(n)
Hash/count table O(n) O(n)
XOR O(n) O(1)

Follow-ups interviewers ask

  1. Two unique numbers, all others twice: XOR everything to get x = a ^ b. Pick any set bit of x (x & -x); a and b differ there. Split the array into two groups by that bit and XOR each group separately.
  2. One number once, all others three times: count each bit position modulo 3, or use the ones/twos bitmask method.
  3. Find the missing number 1..n: XOR all indices 1..n with all elements; the missing one remains. This avoids the overflow risk of the sum formula n(n+1)/2.