Binary crash course ↗ · 46

136. Single Number

Every element appears exactly twice except for one — find that one in O(n) time and O(1) space. The trick is a two-line XOR fold: identical pairs cancel to 0, leaving the lone value standing.

● EasyBit ManipulationXORTypeScript

PROBLEM What we're solving

Given a non-empty array of integers where every element appears twice except for one, return the element that appears only once. No extra memory allowed.

Example: [4, 1, 2, 1, 2] → 4. The pairs (1,1) and (2,2) cancel; 4 has no partner.

KEY IDEA XOR makes pairs disappear

Insight → XOR has two perfect properties: a ^ a = 0 (any value XORed with itself vanishes) and 0 ^ a = a (zero is the identity). XOR every element in the array — all duplicates cancel to 0, and the surviving xor value is the single number. Order does not matter because XOR is commutative and associative.

RECIPE Fold the whole array with XOR

  • 0 · Initialise. Set xor = 0. This is the XOR identity — it will absorb the first real element unchanged.
  • 1 · Fold. For each number n in the array, compute xor ^= n. Every pair (a, a) that appears contributes a ^ a = 0 and collapses away.
  • 2 · Return. After the loop, xor holds exactly the value that had no pair. Return it. No extra data structure needed.
Classic confusion →learners sometimes reach for a hash map to count occurrences, which works but uses O(n) space — violating the constraint. The XOR approach is O(1) space because it keeps only a single integer across the whole scan. If the interviewer says "no extra memory", that's the cue to think XOR, not a map.

COST Complexity & alternatives

Hash map count
O(n) space
O(n) time but stores every unique element.
XOR fold
O(1) space
O(n) time; only one integer variable.

Why XOR works at the bit level

At each bit position, an even number of 1s XORs to 0 and an odd number XORs to 1. Because every duplicate contributes an even count of 1s per bit, only the single number's bits survive.

Pattern transfer → the XOR trick powers several harder variants: Single Number II (each duplicate appears three times — use bit counting mod 3), Single Number III (two unique elements — split on a differing bit and XOR each group), and Missing Number (XOR indices 0…n with the array values).

RUN IT XOR every element — pairs cancel, singleton survives

step 0 / 6
STARTXOR every element together. Pairs will cancel to 0; the lone value survives.
Initialise xor = 0. Input: [4, 1, 2, 1, 2]
1▶function singleNumber(nums: number[]): number {
2▶  let xor = 0;
3  for (const n of nums) {
4    xor ^= n;      // pairs cancel: a ^ a = 0; identity: 0 ^ a = a
5  }
6  return xor;      // only the unpaired element remains
7}
4011221324
State
0
xor
00000000
binary
—
i
—
n
—
xor ^ n
current element (n)already XOR-edresult
slowfast

TYPESCRIPT The solution, annotated

singleNumber.ts
function singleNumber(nums: number[]): number {
  let xor = 0;
  for (const n of nums) {
    xor ^= n;      // pairs cancel: a ^ a = 0; identity: 0 ^ a = a
  }
  return xor;      // only the unpaired element remains
}

Reading it block by block

Line 2 — accumulator. xor starts at 0, the XOR identity. It will absorb every element in one pass.
Lines 3–5 — the fold. Each iteration XORs the accumulator with the next number. Pairs cancel: when the same value a appears twice, xor ^ a ^ a = xor ^ 0 = xor. The lone element has no partner to cancel it.
Line 6 — the result. After every element has been processed, all duplicates have zeroed out. The remaining xor value is the single number. Return it.
Complexity → O(n) time — one pass through the array. O(1) space — one accumulator variable, xor, regardless of input size.

INTERVIEWFollow-ups they'll ask

  • "What if every element appears three times except one?" This is Single Number II. Count each bit position mod 3; any bit that is 1 mod 3 belongs to the unique element. Implement with a ones / twos state machine.
  • "What if there are two unique elements?" This is Single Number III. XOR the whole array to get a ^ b, isolate any differing bit (e.g. diff &= -diff), partition the array on that bit, and XOR each partition separately.
  • "Can you find the missing number in 0…n?" Same pattern — XOR all indices 0…n with all array values; matched pairs cancel and the missing index survives.
  • "Why is sorting not acceptable here?" Sorting is O(n log n) time and mutates the array. XOR is O(n) time, O(1) space, and non-destructive.
  • "What edge cases should you handle?" The problem guarantees exactly one unique element, so an empty array is not valid input. Still worth mentioning: a single-element array trivially returns nums[0] via the XOR loop (zero XOR-ed with one value is that value).

OPTIMAL Bit Manipulation

singleNumber.ts
function singleNumber(nums: number[]): number {
  let xor = 0;
  for (const n of nums) {
    xor ^= n;      // pairs cancel: a ^ a = 0; identity: 0 ^ a = a
  }
  return xor;      // only the unpaired element remains
}
Complexity → O(n) time — one pass through the array. O(1) space — one accumulator variable, xor, regardless of input size.

ALT 1 Brute force — count occurrences in a hash map

O(n) time · O(n) space

Tally how many times each value appears, then return the one whose count is 1. The obvious approach before spotting the XOR trick.

approach-2.ts
function singleNumber(nums: number[]): number {
  const counts = new Map<number, number>();
  for (const n of nums) {
    counts.set(n, (counts.get(n) ?? 0) + 1);
  }
  for (const [value, count] of counts) {
    if (count === 1) return value;
  }
  return -1;   // problem guarantees exactly one unique value
}
Note → Runs in linear time but stores up to n entries — O(n)space, violating the problem's constant-memory constraint. XOR-folding gets the same answer with a single accumulator and O(1) space.

MNEMONIC The one-liner

"XOR is the eraser — every duplicate rubs itself out, leaving only the odd one behind."

TRIGGERS When you see ___ → reach for ___

"every element appears twice except one"XOR fold (O(1) space)
"no extra memory" + find uniquebit manipulation / XOR
pairs that cancel, single survivora ^ a = 0; 0 ^ a = a
"appears k times" for k > 2bit count mod k (generalised XOR trick)

SKELETON The reusable shape

skeleton.ts
function singleNumber(nums: number[]): number {
  let xor = 0;
  for (const n of nums) {
    xor ^= n;
  }
  return xor;
}

FLASHCARDS Tap to flip

What two XOR properties power this solution?
a ^ a = 0 (self-cancellation) and 0 ^ a = a (identity).
tap to flip
1 / 7
Answer to reveal explanations. No penalty for retries.Score: 0 / 9
QUESTION 01
Trace [4, 1, 2, 1, 2] manually. What does the accumulator equal after processing the third element (2)?
QUESTION 02
What is the space complexity of the XOR solution?
QUESTION 03
Why does a ^ a = 0 guarantee correctness for this problem?
QUESTION 04
A candidate uses a hash map to count frequencies and returns the key with count 1. What is the drawback?
QUESTION 05
singleNumber([7]) should return:
QUESTION 06
Which sibling problem asks you to find the single element when every duplicate appears THREE times?
QUESTION 07
XOR is commutative and associative. What does that mean for this algorithm?
QUESTION 08
#136 · Single NumberXOR all numbers together: pairs of identical values cancel to 0, leaving the unique unpaired value as the result. O(n) time, O(1) space — no hash set needed.Which algorithmic approach does this primarily use?
QUESTION 09
#136 · Single NumberXOR all numbers together: pairs of identical values cancel to 0, leaving the unique unpaired value as the result. O(n) time, O(1) space — no hash set needed.Which implementation correctly solves it?