Single Number

Problem

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 a linear runtime complexity and use only constant extra space.

Examples

The brute-force approach

Count the frequency of each number using a hash map. Return the number with count 1.

counts = {}
for n in nums:
    counts[n] = counts.get(n, 0) + 1
for n, c in counts.items():
    if c == 1:
        return n

O(n) time and O(n) space — the hash map stores up to n/2 + 1 entries. The problem requires O(1) space.

Spotting the pattern

This is a Bit Manipulation problem. The key question to ask yourself:

What happens when you XOR a number with itself? What happens to every pair of duplicates?

Answering that is where it clicks, and it's exactly what the guided walkthrough below builds with you: the pattern reasoning, a progressive hint ladder that never spoils the answer, a row-by-row dry run, the optimized solution, and an in-browser editor to run your code against real test cases.