Single Number

Problem

Every element in the array appears exactly twice - except one element that appears only once. Return that unique element in O(n) time and O(1) space.

Input:  [2, 2, 1]              → 1
Input:  [4, 1, 2, 1, 2]        → 4
Input:  [7, 3, 7, 5, 5, 3, 6]  → 6

Verification

Writing assert lines after your solution is a strong interview signal - it shows you test your own work. One assert per example from the problem statement is enough. Add a print to trace intermediate state when an assert fires and you're not sure why.

Solution

Approach - XOR cancellation in a single accumulator.

Initialize result = 0 and fold every element into it with result ^= num. XOR has three properties that make this work: it is self-inverse (a ^ a = 0), 0 is its identity (a ^ 0 = a), and it is commutative and associative so the order of the fold is irrelevant. Because every paired element appears exactly twice, those two appearances XOR against each other and vanish, no matter how far apart they sit in the array. The lone element has no partner, so its bits never get cancelled and it is the only thing left in the accumulator at the end.

Trace [4, 1, 2, 1, 2]: start at 0, then 0^4=4, 4^1=5, 5^2=7, 7^1=6, 6^2=4. The two 1s and two 2s each cancelled to nothing along the way and 4 survived. Mentally you can reorder the fold to (1^1) ^ (2^2) ^ 4 = 0 ^ 0 ^ 4 = 4, which is the same result commutativity guarantees. This beats a hash-map count (O(n) space) and a sort-and-scan (O(n log n) time) by needing just one integer of state.

Edge cases - A single-element array [1] has no pairs; 0 ^ 1 = 1 returns it unchanged via the identity property. The trick relies on every other element appearing an even number of times - it breaks if any duplicate appears three times.

Complexity - O(n) time, O(1) space - one pass over the array updating a single accumulator.