Find the Element That Appears Once (XOR)
Every element of an array appears exactly twice, except one element that appears once. Find that element in O(n) time and O(1) extra memory, without sorting.
Implement int single_number(const int *a, size_t n).
Example: {4, 1, 2, 1, 2} → 4.
Write your code on the right and press Run (or Ctrl + Enter). Hidden tests check your functions and print the result below the editor.
What is x ^ x? What is x ^ 0? XOR is also commutative and associative, so the order of the elements doesn't matter.
#include <stdio.h>
#include <stddef.h>
int single_number(const int *a, size_t n)
{
unsigned int r = 0;
for (size_t i = 0; i < n; i++)
r ^= (unsigned int)a[i]; /* pairs cancel out */
return (int)r;
}
Three properties of XOR do all the work:
x ^ x = 0: every value that appears twice cancels itself.x ^ 0 = x: the value that appears once survives.- XOR is commutative and associative: the pairs don't need to be next to each other.
So XOR-ing the whole array leaves exactly the unpaired element. O(n) time, O(1) memory, no sorting and no hash table.
Walk-through: {4, 1, 2, 1, 2} (binary)
| step | value | r |
|---|---|---|
| start | 000 | |
| ^ 4 | 100 | 100 |
| ^ 1 | 001 | 101 |
| ^ 2 | 010 | 111 |
| ^ 1 | 001 | 110 |
| ^ 2 | 010 | 100 = 4 |
Doing the XOR on unsigned int keeps every bit pattern well defined, including negative numbers.
Follow-ups interviewers ask next:
- Two elements appear once: XOR everything to get
x ^ y, take any set bit (v & -v) to split the array into two groups, and XOR each group. - Every other element appears three times: count each bit position modulo 3.
- Find the missing number in
0..n: XOR all indexes and all values together. - Same trick in firmware: XOR checksums in serial protocols (see UART Packet Parser) and RAID-style parity.
Show the hidden tests
/* ---- tests ---- */
static int fails;
#define CHECK(c) do { if (!(c)) { printf("FAIL line %d: %s\n", __LINE__, #c); fails++; } } while (0)
int main(void)
{
const int a[] = { 4, 1, 2, 1, 2 };
CHECK(single_number(a, 5) == 4);
const int b[] = { 7 };
CHECK(single_number(b, 1) == 7);
const int c[] = { -3, 9, 9, 0, 0 };
CHECK(single_number(c, 5) == -3);
const int d[] = { 2, 2, 0 };
CHECK(single_number(d, 3) == 0);
const int e[] = { 2147483647, 5, -2147483647 - 1, 5, 2147483647 };
CHECK(single_number(e, 5) == -2147483647 - 1);
puts(fails ? "Some tests failed" : "All tests passed");
return fails != 0;
}