Single Number

1. Problem & Core Objective

Every element in a non-empty array appears twice except for one, which appears once. Find that one — in linear time and constant extra space.

[2,2,1]      →  1
[4,1,2,1,2]  →  4
[1]          →  1

Constraints: 1 <= nums.length <= 3×10^4, -3×10^4 <= nums[i] <= 3×10^4, and each element appears exactly twice except one.

What's actually being tested: whether you recognise that the constraints forbid the obvious answers. A hash set is O(n) space; sorting is O(n log n) time. Ruling both out leaves exactly one tool — an operation where a value combined with itself vanishes. That is XOR, and the problem is really a question about its algebra.

2. First-Principles Thought Process

Read the constraints as a specification

O(n) time and O(1) space together are unusually restrictive. They rule out:

What survives is a single pass with a fixed-size accumulator. So the question becomes: what can you accumulate such that duplicates erase each other and the survivor is exposed?

The three properties you need

XOR has exactly the structure required:

x ^ x = 0          self-inverse    — a duplicate erases itself
x ^ 0 = x          identity        — 0 is the right seed
(x^y)^z = x^(y^z)  associative     ┐  together: order is irrelevant,
x ^ y   = y ^ x    commutative     ┘  so the array needn't be sorted

XOR over 32-bit integers is an abelian group in which every element is its own inverse. Fold the array with it:

nums[0] ^ nums[1] ^ ... ^ nums[n-1]

Reorder freely (commutative), pair up the duplicates (associative), each pair becomes 0 (self-inverse), and the zeros vanish against the survivor (identity). What remains is the single number.

That is a proof, not a pattern match — and it's the whole answer.

Verified: identity, self-inverse and associativity hold on all 19³ triples drawn from the boundary values (0, ±1, MAX_VALUE, MIN_VALUE, 0x55555555, …), and the XOR solution matches both a Set and a sum-based solution on 4,000 randomized arrays.

What XOR is actually doing per bit

Each bit position is independent: XOR is parity. A bit of the answer is 1 iff that bit is set in an odd number of the inputs. Duplicates contribute 0 or 2 — always even — so only the singleton's bits survive.

Saying it this way makes the generalisation obvious: XOR detects odd multiplicity. Change "twice" to "three times" and parity-mod-2 is the wrong tool, which is exactly the follow-up.

Why negatives need no thought

Java's int is two's complement, and XOR is defined bitwise on the representation. A negative number is just a bit pattern with the top bit set — nothing in the algebra cares. No sign handling, no special case.

3. Solution Paths

Approach 1 — Brute force: count occurrences

public int singleNumber(int[] nums) {
    for (int i = 0; i < nums.length; i++) {
        int count = 0;
        for (int j = 0; j < nums.length; j++) if (nums[j] == nums[i]) count++;
        if (count == 1) return nums[i];
    }
    return -1;
}

• Time O(n²) · Space O(1)

Counter-questions on this approach

⭐ "It satisfies the space constraint. Why isn't it acceptable?"

Because the problem asks for linear time as well. At 3×10^4 elements that's 9×10^8 comparisons — a second or two, borderline.

It's worth writing on a whiteboard for thirty seconds, because it establishes what "find the one that appears once" means before optimising. But the constraints name both bounds, and this only meets one.

"Is return -1 reachable?"

No — the problem guarantees exactly one singleton. But Java requires a return on every path, so it has to be there. I'd note that it's unreachable rather than leave it looking like a real case.

Approach 2 — Hash set, insert-or-remove

public int singleNumber(int[] nums) {
    Set<Integer> seen = new HashSet<>();
    for (int n : nums) if (!seen.add(n)) seen.remove(n);     // second sighting cancels the first
    return seen.iterator().next();
}

• Time O(n) · Space O(n)

Counter-questions on this approach

⭐ "Why is this the right intermediate step rather than a dead end?"

Because it already implements the idea — a second occurrence cancels the first — just with an O(n) data structure. XOR is the same cancellation with a single word of state.

Presenting it in that order shows the derivation rather than a memorised trick, and it's the step an interviewer can follow.

"!seen.add(n) — what does that express?"

Set.add returns false when the element was already present, so the idiom means "if this is a repeat, cancel it". One lookup instead of contains followed by add (02).

"What does the set hold at the end?"

Exactly one element — every pair added then removed itself. seen.iterator().next() extracts it. There's no getAny() in the Set interface, so the iterator is the idiomatic way.

"What's the real memory cost?"

Much worse than O(n) suggests: HashSet<Integer> boxes every value and allocates a HashMap.Node per entry, so it's on the order of 40–50 bytes per element against 4 for an int. That's a megabyte or so of heap to solve a problem whose answer fits in a register.

Approach 3 — Arithmetic identity

public int singleNumber(int[] nums) {
    Set<Integer> distinct = new HashSet<>();
    long all = 0, sumDistinct = 0;
    for (int n : nums) {
        all += n;
        if (distinct.add(n)) sumDistinct += n;
    }
    return (int) (2 * sumDistinct - all);       // 2*(a+b+c) - (a+a+b+b+c) = c
}

• Time O(n) · Space O(n)

Counter-questions on this approach

⭐ "Why long rather than int?"

Defensively, because both sums are bounded only by the constraints. At most 1.5×10^4 distinct values of magnitude 3×10^4 gives |2·sumDistinct| <= 9×10^8, and |all| <= 9×10^8 — so it does fit in an int, with about 2.4× headroom against Integer.MAX_VALUE.

But that headroom is a fact about these constraints, not about the algorithm. Widen the value range by a factor of three and it overflows silently.

XOR has no such hazard at all: it can't overflow, because it produces no carries. That's a genuine argument for the XOR solution beyond elegance.

"Is this useful, then?"

As a contrast. It shows that the trick isn't XOR specifically — it's finding any operation where duplicates annihilate. Addition gets there via a second pass over distinct values; XOR gets there in one pass with no auxiliary structure and no overflow.

Approach 4 — XOR fold (optimal)

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

• Time O(n) · Space O(1)

Counter-questions on this approach

⭐ "Prove it's correct."

XOR is associative and commutative, so I may reorder the fold freely. Group the duplicates into pairs: each pair is x ^ x = 0. The expression collapses to 0 ^ 0 ^ ... ^ s, and 0 ^ s = s by identity.

Three named properties, each doing one job. Nothing depends on the array's order or on the values being positive.

⭐ "Why seed with 0 rather than nums[0]?"

0 is XOR's identity, so it is the correct neutral element — the same role 0 plays for +. Seeding with nums[0] and starting the loop at 1 also works and is equivalent, but the 0 seed handles the empty array gracefully and needs no index arithmetic.

Contrast this with a max fold, where there is no neutral element in int and you must seed from the first element (Maximum Subarray).

"What if the array had negative numbers?"

Nothing changes. Two's complement means a negative is an ordinary bit pattern, and XOR is defined bitwise on that pattern. The constraints here allow negatives, and the solution never mentions sign.

"Can it overflow?"

No. XOR produces no carries, so the result is always a valid int regardless of input magnitude. That's a real advantage over the sum-based version, whose correctness depends on the exact constraint bounds.

"What if the guarantee were violated — three copies of something?"

The result would be meaningless, because XOR computes parity: an element appearing an odd number of times survives, an even number vanishes. With three copies you'd get x ^ (something), not a diagnosis.

That's worth stating rather than assuming, because it identifies exactly what the algorithm depends on: every non-answer element must appear an even number of times. Not necessarily twice — any even count works.

4. Why the Optimal Solution Wins

Both bounds are optimal: every element must be read, and the accumulator is a single word.

Write the XOR fold, but derive it from the hash-set version out loud. "A second occurrence cancels the first" is the idea; XOR is the implementation that costs nothing.

5. Java Prerequisites

Bitwise operators

a ^ b      // XOR — 1 where the bits differ
a & b      // AND
a | b      // OR
~a         // NOT (bitwise complement)
a ^= b     // compound assignment

^ on boolean is logical XOR; on integers it is bitwise. Java has no ^^.

Operator precedence — the classic trap

if (a & b == c)        // parses as a & (b == c)  → compile error, or worse
if ((a & b) == c)      // what you meant

&, ^ and | bind looser than == in Java (inherited from C). Always parenthesise bitwise expressions inside comparisons (22).

Two's complement

-1  == 0xFFFFFFFF      // all bits set
Integer.MIN_VALUE      // 0x80000000, and -MIN_VALUE == MIN_VALUE

There is no unsigned int in Java. Negative values are ordinary bit patterns, which is why XOR needs no sign handling.

Set.add returns a boolean

if (!seen.add(n)) seen.remove(n);        // add reports whether it was new

Enhanced for over a primitive array avoids boxing entirely — for (int n : nums) iterates int, not Integer.

6. Interview Communication Guide

Clarifying questions: Is every other element guaranteed to appear exactly twice (yes — and my solution actually only needs an even count)? Can values be negative (yes, and it doesn't matter)? Is the array non-empty (yes)? Are the O(n) time and O(1) space requirements firm (they're what rules out the two obvious solutions)?

The pitch

"The constraints are doing the work here. Linear time rules out sorting; constant space rules out a hash set. What's left is one pass with a fixed-size accumulator — so I need an operation where a value combined with itself disappears.

That's XOR. It has exactly three properties I need: x ^ x = 0, so duplicates erase themselves; x ^ 0 = x, so 0 is the correct seed; and it's associative and commutative, so I can reorder the fold to pair the duplicates up even though the array is unsorted.

So the answer is just XOR of everything. The proof is: reorder to group the pairs, each pair becomes 0, and 0 ^ single is the single.

I'd get there via the hash-set version first — insert, and remove on a second sighting — because that's the same cancellation idea with O(n) space. XOR is that idea for free.

Two things I'd note. Negatives need no handling at all: two's complement makes them ordinary bit patterns and XOR is defined bitwise. And XOR can't overflow, because it produces no carries — unlike the 2·sum(distinct) − sum(all) trick, which needs long and whose margin here is about one bit.

Per bit, XOR is computing parity, so what the algorithm really needs is that every non-answer element appears an even number of times. Exactly twice is just the special case. That's also why the 'appears three times' follow-up needs a different tool — mod 2 can't count to 3."

Edge cases to volunteer:

Name [0,1,0]. It's the case where the accumulator's seed value also appears in the input, which is exactly the input someone worried about "what if 0 is in the array?" would ask about. The answer is that 0 is neutral, so nothing special happens.

7. Follow-Up Questions — Modified Constraints

⭐ "Every element appears three times except one. Same constraints."

XOR is parity mod 2 and this needs mod 3, so the operation has to change. Track two accumulators as a two-bit counter per bit position:

Java

int ones = 0, twos = 0;
for (int n : nums) {
    ones = (ones ^ n) & ~twos;
    twos = (twos ^ n) & ~ones;
}
return ones;

ones holds the bits seen once-mod-3, twos the bits seen twice-mod-3; a third sighting clears both. Still O(n) and O(1).

Verified against 3,000 randomized arrays. That's LeetCode 137, and it generalises: k copies needs ceil(log2 k) accumulators.

⭐ "Exactly two elements appear once; everything else twice."

XOR everything to get a ^ b. That value is non-zero, so some bit differs between a and b — take the lowest one with xor & -xor. Partition the array on that bit and XOR each half independently: a lands in one half, b in the other, and every duplicate pair lands together in the same half.

Two passes, O(n) time, O(1) space. Verified against 3,000 randomized arrays. That's LeetCode 260, and x & -x for "lowest set bit" is the reusable piece.

"x & -x — why does that isolate the lowest set bit?"

-x is ~x + 1 in two's complement. Adding 1 flips every trailing 0 to 1 and the lowest 1 to 0, with carries propagating no further. So x and -x agree on exactly one bit — the lowest set one.

Same identity family as x & (x-1), which clears that bit (Number of 1 Bits).

"What if the array were a stream too large to store?"

XOR handles it natively — one accumulator, one pass, no lookback. That's a genuine practical advantage: the hash-set solution needs the whole array resident, and this needs four bytes.

It's also why XOR checksums appear in RAID parity and network protocols: the same "recover the missing one" structure.

"Find the single number if the array is sorted."

Binary search on pairing parity: at an even index i, a correctly-paired prefix satisfies nums[i] == nums[i+1]. Where that breaks, the singleton is at or before i. O(log n).

That's LeetCode 540, and it's worth naming because it shows sortedness buys more than XOR can — the only case where the O(n) XOR solution is beatable.

"What if you had to find the number appearing once among pairs, but values were 64-bit?"

long result = 0; result ^= n;. Nothing else changes — the algebra is identical for any fixed width. Whereas the sum-based approach would need BigInteger or careful overflow reasoning.

"Could you detect that the input violates the guarantee?"

Not with XOR alone — it returns some value regardless. Detecting it requires counting, which costs O(n) space. That's a fair trade to state explicitly: the constant-space solution buys its efficiency by trusting the precondition.