The Lone Number

Difficulty: Easy · Pattern: Bit Manipulation · Concept: General Coding (DSA) — Core Patterns to Drill

Given a non-empty list of integers where every element appears exactly twice except for one, which appears exactly once, find that one element.

A hash-map count gets there in $O(n)$ time and $O(n)$ space. Bit manipulation gets the same time complexity with $O(1)$ space — no auxiliary structure at all — by exploiting one property of XOR (^): $x \oplus x = 0$ for any $x$, and XOR is commutative and associative, so order doesn't matter.

Your task: implement lone_number(nums) using only XOR — no dictionary, no set.

Next: The Two Lone Numbers (a harder variant), or continue to The Gap in the Sequence