174 — Single Number

174 — Single Number

LeetCode 136 · Easy. You're given a non-empty array of integers nums where every element appears exactly twice except for one element, which appears exactly once. Find that single element. Your algorithm should run in O(n) time and, ideally, use only O(1) extra space.

---

🍽️ Intuition

Picture a box of socks where every sock has an identical partner, except one lonely sock that came from a completely different pair. If you could pair up every matching sock and toss both into a bag together, whatever's left standing alone at the end is your answer. Counting is one way to find that lonely sock — tally how many times each one shows up, then report the one with a tally of exactly one. But there's a slicker move available here because the "partners" are identical values, not just similar ones: XOR any value with itself and you get zero. Line up every number in the array and XOR them all together, and every matched pair cancels itself out — a ^ a = 0 — leaving nothing behind but the lonely number.

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

4 ^ 1 ^ 2 ^ 1 ^ 2
= 4 ^ (1 ^ 1) ^ (2 ^ 2)
= 4 ^    0    ^    0
= 4                       <- the single number

---

🚩 Pattern-Recognition Cue

"Every element appears twice except one" is the signature of an XOR-cancellation problem: whenever a value's duplicate is what needs to disappear, and the operation you'd use to detect "is this a duplicate?" would otherwise cost you a hash map, check whether XOR's self-canceling property (a ^ a = 0, a ^ 0 = a) can eliminate the pairs directly instead of counting them.

---

🐢 Brute Force

Count how many times each number appears using a hash map, then scan the map for the one entry with a count of exactly one.

func singleNumberBruteForce(_ nums: [Int]) -> Int {
    var counts: [Int: Int] = [:]
    for num in nums {
        counts[num, default: 0] += 1
    }

    for (num, count) in counts where count == 1 {
        return num
    }

    return -1   // unreachable given the problem's guarantee
}

// smoke test
print(singleNumberBruteForce([4, 1, 2, 1, 2]))   // 4
print(singleNumberBruteForce([2, 2, 1]))          // 1
print(singleNumberBruteForce([1]))                // 1

Big-O: O(n) time to build and scan the map. O(n) extra space for the hash map, which can hold up to n / 2 distinct keys.

---

🚀 Optimal

XOR every element in the array together. Matched pairs cancel to 0, and XOR-ing anything with 0 leaves it unchanged, so the running result converges on the single number.

func singleNumber(_ nums: [Int]) -> Int {
    var result = 0
    for num in nums {
        result ^= num
    }
    return result
}

// smoke test — same cases as the brute force
print(singleNumber([4, 1, 2, 1, 2]))   // 4
print(singleNumber([2, 2, 1]))          // 1
print(singleNumber([1]))                // 1

Big-O: O(n) time — one pass, one XOR per element. O(1) extra space — just the running accumulator.

---

🔑 The Key Insight

The brute force's hash map exists purely to answer "how many times has this value shown up?" — but XOR already tracks a version of that question for free, without needing any storage. Because XOR is commutative and associative, the order elements arrive in doesn't matter, and because a ^ a = 0, every duplicate pair silently erases itself as soon as it's fully seen. What survives at the end isn't a lookup result pulled from a table — it's just whatever didn't have a partner to cancel it out.

---

🔗 Related Chapters

• Hash Maps and Hash Sets — the counting structure the brute force uses to tally occurrences before scanning for the one with count 1.
• Bit Manipulation Tricks — the XOR self-cancellation trick (a ^ a = 0, a ^ 0 = a) that the optimal solution runs on.

---

🧸 Memory Sentence

Single Number is a box of socks where every pair cancels out under XOR — whatever's left standing alone at the end is the answer.

---

✅ Check Your Understanding

1. Why does the order in which you XOR the elements together not matter, even though the array itself has no guaranteed ordering?
2. What would go wrong with the XOR approach if the problem instead guaranteed every element appears three times except one — why does XOR's cancellation stop working there?
3. Trace result through singleNumber([2, 2, 1]) step by step and confirm it lands on 1.
4. The brute force's hash map holds a count for every distinct value, not just the duplicates. Why can't it stop early and skip building an entry for a value it has already seen exactly twice?

---

⬅️ Previous: Detect Squares · Next: Number of 1 Bits ➡️