Every element appears twice except one. Find the element that appears once, in O(n) time and O(1) space.
Recognizing XOR as the tool for 'pairs cancel out' problems instead of reaching for a hash set.
XOR has three properties that make this a one-liner: x ^ x === 0 (a value cancels itself), x ^ 0 === x (identity), and it is commutative and associative (order doesn't matter). So XOR-ing every element together cancels each duplicated pair and leaves only the unique value. Signal: 'everything appears an even number of times except one' → fold with XOR. This beats a hash set (which costs O(n) extra space) and sorting (O(n log n)). The same trick finds a missing number (XOR the values against the full index range) and swaps two variables without a temp.
'Appears twice / even count except one', parity checks, toggling flags, or swapping without a temp.
Time O(n), Space O(1)