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.

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)

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

• Invariant: the running XOR equals the XOR of all processed elements.
• Bitwise operations preserve the required per-bit invariant.
• Combining results across bits reconstructs the correct value.
• Therefore the final bit-accumulated result is correct.

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).

Complexity

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

Implementation notes (Go)

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