Given a non-empty array of integers nums, every element appears twice except for one. Find that single one. You must implement a solution with O(n) time complexity and O(1) extra space.
Constraints: 1 ≤ nums.length ≤ 3 × 10⁴ · -3 × 10⁴ ≤ nums[i] ≤ 3 × 10⁴ · Each element appears twice except for one.
Imagine you have a bag of socks. Every sock has a twin somewhere in the pile — except one lonely orphan. You need to find it.
In code, that translates to: given nums = [4, 1, 2, 1, 2], every integer appears exactly twice except for one. Find the unique element. But here is the catch — you must do it in O(n) time with O(1) extra space. One pass. No auxiliary data structures.
That second constraint is the teeth. Most problems let you trade space for speed. This one says: no. You get a single integer variable and one scan through the array. If you have never seen the trick, this feels impossible. Let us see why.
Interviewers love this problem because it tests whether a candidate can escape the hash map reflex. In most array problems, “count occurrences” is a safe first move — build a frequency map, scan for the answer, done. That approach works here for correctness, but it uses O(n) auxiliary space. The interviewer is watching for the moment you recognize that the standard toolkit is insufficient — and whether you can reason about the problem at a lower level of abstraction. Bit manipulation problems are rare in interviews, but when they appear, they almost always have this structure: a familiar problem with a constraint that blocks all conventional approaches, forcing you to think about the binary representation of your data.
Your first instinct is probably to count occurrences. Tap each approach below to test it against the dual constraints.