Topics / Bit Manipulation / Q20
How do you find the single number that appears once when all others appear twice?
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
- Two unique numbers, all others twice: XOR everything to get
x = a ^ b. Pick any set bit ofx(x & -x);aandbdiffer there. Split the array into two groups by that bit and XOR each group separately. - One number once, all others three times: count each bit position modulo 3, or use the
ones/twosbitmask method. - 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.