Single Number

Given a non-empty array where every element appears twice except for one, return that single one. A frequency map works but uses extra space.

Why this is worth learning

XOR is a cancellation operation over each bit position. Commutativity lets equal pairs cancel even when their occurrences are far apart in the input.

Before coding: one-minute experiment

For [-7,4,4], why does XOR return -7 even though its signed representation has many leading one bits?

Function signature

func SingleNumber(nums []int) int

Inputs / outputs

• nums: array of integers.
• Return: the element that appears once.

Example

nums = [4,1,2,1,2]
Output: 4

Constraints

• 1 <= len(nums) <= 100_000

Core idea (near-solution)

A frequency map solves the multiplicity promise directly. For constant extra space, seek a summary where identical pairs cancel in any order. Addition and OR do not have that property; XOR does, because x XOR x=0 and XOR with zero preserves a value. This algebra derives the fold and also explains its limit: two different singleton values would survive as their XOR, not as one of them.

XOR cancels pairs: a ^ a = 0, a ^ 0 = a. XOR all numbers to isolate the single element.

Invariant: the running XOR equals the XOR of all processed elements.

Algorithm (step-by-step)

1. Initialize res = 0.
2. For each value v, do res ^= v.
3. Return res.

Correctness sketch

The running accumulator is the XOR of every processed entry. XOR is associative and commutative, x XOR x is zero, and x XOR zero is x. Therefore the final expression can be regrouped into zero-valued pairs plus the one unpaired value. This holds for signed values as bit patterns as well as positive values. The proof depends on the exact multiplicity promise; with several singleton values the result would be their XOR, not one selected singleton.

Trace (hand walkthrough)

Example input:
nums = [4,1,2,1,2]
Output: 4

Walk:
- 4^1=5, 5^2=7, 7^1=6, 6^2=4
- result = 4

Pitfalls to avoid

• Trying to sort or use a map (unnecessary).

Debugging lens

Do not deduplicate the input before the fold. Test a singleton zero, negative values, and pairs separated by other values. Missing multiplicity guarantees cannot be validated by this algorithm alone.

Complexity

• Time: O(n).
• Extra space: O(1).

Implementation notes (Go)

• Works for negative numbers as XOR operates on two's complement bits.

Reconstruction checkpoint

For [-7,4,4], why does XOR return -7 even though its signed representation has many leading one bits?

Return to Bit Manipulation · Module quiz