Single Number (LC 136)

Pattern: Bit manipulation (XOR) — not cyclic sort, but same “array with duplicates / uniqueness” family
Difficulty: Easy
Key Concept: XOR is commutative and associative, and a ^ a = 0, a ^ 0 = a, so pairing duplicates cancels them and leaves the singleton.

Problem Statement

Given a non-empty integer array nums where every element appears exactly twice except for one element that appears once, find that single element.

Your algorithm must run in linear time and use only constant extra space.

Input: int[] nums (non-empty, one unique value, all others appear twice).
Output: The integer that appears once.

Example: nums = [4,1,2,1,2] → 4.

---

1. Algorithm & Pseudocode

Brute force (frequency map)

build map count from value -> frequency
for each entry in count:
    if frequency == 1:
        return that key

Optimal (XOR)

result = 0
for each x in nums:
    result = result XOR x
return result

Why duplicates vanish: For each value a that appears twice, contributions a ^ a are 0. Order does not matter because XOR is commutative and associative.

---

2. Step-by-Step Analysis (Beginner-Friendly)

Why brute force is correct: Counting occurrences with a HashMap identifies the key with count 1.

Why brute force violates the “constant space” follow-up: The map can grow with distinct values → O(n) extra space.

Why XOR works: Think of XOR as “flip bits where bits differ.” Identical numbers have identical bits, so XORing them yields zero. The lone number has no partner, so nothing cancels it.

Properties to memorize:

• x ^ x = 0
• x ^ 0 = x
• (a ^ b) ^ c = a ^ (b ^ c) (associative)
• a ^ b = b ^ a (commutative)

Why this is not cyclic sort: There is no guarantee values lie in 1..n or map cleanly to indices; the bit trick stands alone. It still sits mentally beside “find missing/duplicate” problems because it exploits pairing structure.

---

3. The Dry Run

Sample: nums = [4, 1, 2, 1, 2]
We trace result after XORing each element in order.

Step	Element x	result before	result after (result ^ x)
1	4	0	4
2	1	4	5 (binary: 100 ^ 001 = 101)
3	2	5	7 (101 ^ 010 = 111)
4	1	7	6 (111 ^ 001 = 110)
5	2	6	4 (110 ^ 010 = 100)

Final result: 4 — the single number.

Pairing intuition: The two 1s XOR to 0 in any order; the two 2s XOR to 0; only 4 remains.

---

4. Java Solution

Brute Force

Time: O(n) — single pass to build counts (amortized O(1) per insert).
Space: O(n) — map size bounded by distinct values.

import java.util.*;

class Solution {
    public int singleNumber(int[] nums) {
        Map<Integer, Integer> freq = new HashMap<>();
        for (int x : nums) {
            freq.put(x, freq.getOrDefault(x, 0) + 1);
        }
        for (Map.Entry<Integer, Integer> e : freq.entrySet()) {
            if (e.getValue() == 1) {
                return e.getKey();
            }
        }
        return -1; // unreachable given problem constraints
    }
}

Optimal

Time: O(n) — one pass.
Space: O(1) — only int result.

class Solution {
    public int singleNumber(int[] nums) {
        int result = 0;
        for (int x : nums) {
            result ^= x;
        }
        return result;
    }
}

---

5. The “Java vs. Others” Edge

• Operator: Java uses ^ for bitwise XOR on int (and other integral types). C++ uses ^ the same way. Python also uses ^ for integers.
• No unsigned confusion: For LC 136, values fit typical 32-bit signed range; XOR still behaves predictably in Java’s two’s-complement int.
• Memorize the pattern: This is one of those small tricks interviewers expect when they say “constant space, linear time” for this exact constraint (pairs + one single).
• Contrast with cyclic sort: Cyclic sort needs the value↔index relationship 1..n; XOR needs only the “even count except one” structure.

---

6. Complexity Summary

Approach	Time	Space	Notes
Brute Force	O(n)	O(n)	HashMap frequency count; simple but extra space.
Optimal	O(n)	O(1)	XOR cancellation; order-independent due to XOR laws.