easy Single Number

Single Number

You are handed an array of integers in which every value appears exactly twice, except one value that appears once. Return that lone value. Example: [4, 1, 2, 1, 2] → 4. The interviewer will usually add the real constraint out loud: do it in linear time and constant extra space. That last clause is the whole game — it quietly rules out the obvious answers and points at exactly one tool: XOR.

The naive baselines (and why they cost)

• Hash set / frequency map. Walk the array; add a value on first sight, remove it on second sight; the one element left in the set is the answer. Or count occurrences and find the count-1 key. Correct and readable, but it costs O(n) time and O(n) extra space — it violates the constant-space constraint.
• Sort, then scan. After sorting, the duplicates sit side by side, so the loner is the element whose neighbours don't match it. That is O(n log n) time, and either O(1) or O(n) space depending on the sort — slower, and it destroys input order.

Both work. Neither hits O(n) time and O(1) space. To get both, we stop tracking which numbers we've seen and instead accumulate a single running value that has the duplicates cancel themselves out. That accumulator is XOR.

The insight — why XOR isolates the loner (the proof)

XOR (^) has three algebraic properties, and together they are the entire solution:

• Self-inverse: a ^ a = 0. A value XORed with itself is all-zero bits — every bit position has two equal bits, and equal bits XOR to 0.
• Identity: a ^ 0 = a. XORing with zero changes nothing.
• Commutative & associative: a ^ b = b ^ a and (a ^ b) ^ c = a ^ (b ^ c). So we may reorder and regroup the XOR of the whole array however we like — the result is unaffected by order.

Now XOR the entire array into one accumulator. Because we can reorder freely, mentally pull each duplicated pair next to itself. Every pair v ^ v collapses to 0 by self-inverse. What remains is 0 ^ 0 ^ … ^ loner, which by identity is just the loner. The duplicates annihilate themselves; the odd-one-out is the only thing that survives. No bookkeeping, one register, one pass.

Traced worked example — [4, 1, 2, 1, 2]

Keep a running accumulator acc, start at 0, XOR each element in array order. Watching the bits change is the point — notice the duplicates walking the accumulator right back to where it was:

Final acc = 100₂ = 4. Notice steps 2&4 (the two 1s) and steps 3&5 (the two 2s) each toggled a bit on then back off — net zero. Only the bit set by 4, which was never toggled a second time, remained. That is the cancellation proof made concrete.

Java: XOR fold

class Solution {
    public int singleNumber(int[] nums) {
        int acc = 0;
        for (int x : nums) {
            acc ^= x;          // duplicates cancel to 0; the loner survives
        }
        return acc;
    }
}

Go: XOR fold

package main

import "fmt"

func singleNumber(nums []int) int {
    acc := 0
    for _, x := range nums {
        acc ^= x // duplicates cancel to 0; the loner survives
    }
    return acc
}

func main() {
    fmt.Println(singleNumber([]int{4, 1, 2, 1, 2})) // 4
}

Complexity — derived from the code

One for loop over n elements; the body is a single XOR and assignment, each a one-cycle CPU instruction — O(1) per iteration. Total time = O(n). We keep exactly one int accumulator regardless of input size, so space = O(1). That is strictly better on memory than the hash-set baseline (O(n) space) and strictly better on time than the sort baseline (O(n log n)), and it needs only a single pass.

Judgment layer — when to reach for XOR, and when the hash set wins

• Reach for XOR when the problem literally guarantees the "everything pairs up except one" structure and demands O(1) space. That pairing is the precondition the whole trick rests on — XOR is the textbook answer and interviewers expect you to know it.
• Prefer the hash set / frequency map when the constraint is different or fuzzier: elements might appear three times, or k times, or you must also report how many times, or return all elements with an odd count, or the input isn't integers you can XOR. A hash map handles every one of those with a one-line change; XOR handles none of them without a redesign. If O(n) space is acceptable, the map is the more robust, more readable, more extensible answer — and in an interview, saying "I'd start with a frequency map for clarity, then note XOR collapses it to O(1) space given the exactly-twice guarantee" signals both pragmatism and depth.
• The trade you are making: XOR buys O(1) space and elegance but is brittle — it exploits one very specific structural fact. The hash set costs O(n) space but is general. Match the tool to how likely the constraints are to shift.

Edge cases & traps

• Single-element array [7]: 0 ^ 7 = 7. Correct with no special-casing — the identity property handles it for free.
• Negative numbers [-1, -1, -3]: XOR operates bitwise on the two's-complement representation, so -3 falls out correctly. No sign handling needed; XOR doesn't care whether a bit pattern "means" a negative number.
• Order independence: because XOR is commutative and associative, the array may be shuffled arbitrarily — same answer. Don't waste effort sorting first.
• The pairing assumption is load-bearing: if some value actually appears an even number of times > 2, or three times, the XOR fold silently returns garbage rather than erroring. Confirm the "exactly twice except one" guarantee before trusting it — this is the exact seam that Single Number II (values appear three times) exploits, where XOR alone no longer works.

Takeaways

• XOR-fold the array: pairs annihilate (a^a=0), the loner survives (x^0=x). O(n) time, O(1) space, one pass.
• The trick is exactly as strong as the "everything appears twice except one" promise — no stronger.
• If constraints could drift (k copies, counts, non-integers), the hash-set answer is the safer engineering call despite its O(n) space.

Authored from first principles on the XOR self-inverse/identity/associativity laws; both samples compiled and hand-traced on [4,1,2,1,2] → 4.