Skip to content

Volume ITechnology

4.30.1 — Single Number ​

LeetCode 136 · Easy · ★ Blind 75

The problem ​

Every element appears twice except one, which appears once. Find it. You must use O(n) time and O(1) space.

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

The pattern ​

The O(1) space requirement rules out a hash set, a counter and sorting-with-a-copy. What is left is arithmetic on the values themselves.

XOR every element together.

Three properties do all the work:

x \oplus x = 0 \qquad x \oplus 0 = x \qquad \text{order does not matter}

So every pair cancels to 0, leaving 0 ^ single = single. The order is irrelevant, which means one pass with no bookkeeping.

The solution ​

python
class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        result = 0  # (1)
        for n in nums:  # (2)
            result ^= n  # (3)
        return result  # (4)
ts
function singleNumber(nums: number[]): number {
  let result = 0;  // (1)
  for (const n of nums) result ^= n;  // (2) (3)
  return result;  // (4)
}

Line by line ​

This uses XOR, written ^. XOR compares two numbers bit by bit. Each bit of the answer is 1 when the two bits differ, and 0 when they are the same. Two facts follow, and they are all this solution needs.

  • Any number XOR itself is 0, because every bit matches: a \oplus a = 0.
  • Any number XOR 0 is itself, because XOR with 0 changes nothing: a \oplus 0 = a.

The order does not matter either: a \oplus b \oplus a is the same as a \oplus a \oplus b.

(1) Start at 0.

(2) Go through every number.

(3) XOR it in. Every number that appears twice meets its twin somewhere in the chain, and the pair cancels to 0. Only the number that appears once is left over.

(4) What is left is the single number.

Trace ​

Take [4, 1, 2, 1, 2]. In binary: 4 is 100, 1 is 001, 2 is 010.

Numberresult beforeresult after (binary)After (decimal)
40001004
11001015
21011117
11111106
21101004

The answer is 4.

Python also has a one-line version:

python
from functools import reduce
from operator import xor
return reduce(xor, nums)

Starting at 0 is what makes it work, since 0 ^ x = x. It is the identity element for XOR, exactly as 0 is for addition.

Trace ​

[4,1,2,1,2]

4 ^ 1 ^ 2 ^ 1 ^ 2. Reorder freely: 4 ^ (1^1) ^ (2^2) = 4 ^ 0 ^ 0 = 4 ✓.

The reordering is legal because XOR is commutative and associative — and that is precisely why the array's order does not matter.

Edge cases ​

  • One number. It is the answer.
  • Negative numbers. XOR works on their bit patterns the same way, and pairs still cancel.

Complexity ​

O(n) time, O(1) space.

Why not sum-based arithmetic? ​

A tempting alternative: 2 × sum(set(nums)) − sum(nums). It works, and it needs O(n) space for the set — so it fails the constraint. It can also overflow on large values, while XOR never can.

XOR never overflows, because it is bitwise and never produces a bit that was not already in range. That is a genuine advantage worth mentioning.

The variants, and where they get interesting ​

Single Number II (LeetCode 137) — every element appears three times except one. XOR no longer cancels, because three copies leave one behind.

The fix generalises the idea: count the set bits at each position across all numbers, then take each count modulo 3. A bit belonging to the tripled numbers appears a multiple of three times; a bit of the single number leaves a remainder.

python
result = 0
for bit in range(32):
    count = sum((n >> bit) & 1 for n in nums)
    if count % 3:
        result |= (1 << bit)

O(32n) time and O(1) space. There is a clever two-variable version using ones and twos, but the bit-counting version is the one you can derive under pressure and explain.

Single Number III (LeetCode 260) — two numbers appear once, the rest twice.

XOR everything and you get a ^ b, the two answers combined. Now use x & -x to isolate any bit where they differ — that bit is 1 in one answer and 0 in the other. Partition the array by that bit and XOR each half separately.

python
xor_all = 0
for n in nums: xor_all ^= n
lowest = xor_all & -xor_all          # a bit where a and b differ
a = b = 0
for n in nums:
    if n & lowest: a ^= n
    else: b ^= n
return [a, b]

That partition-by-a-differing-bit move is the transferable idea, and it is why x & -x is worth having in your fingers.

Where this goes next ​

  • Missing Number — XOR the indices with the values. 4.30.5.
  • Find the Duplicate Number — when mutation and extra space are both banned, XOR does not help and it becomes cycle detection. 4.9.8. Knowing when XOR does not apply is as useful as knowing when it does.
  • Checksums and parity bits — a parity bit is the XOR of a message's bits, and it detects any single-bit flip. Chapter 1.8 covers error detection properly.
  • RAID 5 — the parity disk stores the XOR of the others, so any one failed disk can be reconstructed. The same cancellation, at hardware scale.

What the interviewer will push on ​

"Why does XOR work?" The three properties. Say all three; the commutativity is what makes order irrelevant.

"Why start at 0?" It is XOR's identity.

"What if every element appeared three times?" Count bits modulo 3.

"What if two numbers appeared once?" XOR everything, isolate a differing bit with x & -x, partition, XOR each half.

"Why not sum-based arithmetic?" It needs a set, and it can overflow.

One thing to volunteer: mention RAID parity. It shows the cancellation property is a real engineering tool, not a puzzle trick.

Next: 4.30.2 Number of 1 Bits — counting set bits, and the idiom that makes it fast.

Combine chapters into one PDF

Pick the chapters you want. They print in the order you pick them.

Volume I — Technology
Part 0 — Retention & Notation
Part 1 — Foundations of Computation
Part 2 — Operating Systems
2.1 The Kernel
2.2 Processes
2.3 Threads & Scheduling
2.4 Concurrency Under the Hood
2.5 Memory Management
2.6 File Systems
2.7 Input/Output
2.8 Linux for Engineers
2.9 Windows & macOS in Practice
Part 3 — Languages, Compilers & Runtimes
3.6 JavaScript & V8
3.7 TypeScript
3.8 Node.js Internals
3.13 Python & CPython
3.14 FastAPI & Production Python
Part 4 — Data Structures & Algorithms
4.0 Classic Problems — Before NeetCode
4.4 Arrays & Hashing — Problems
4.5 Two Pointers
4.6 Sliding Window
4.8 Stack — Problems
4.9 Linked List — Problems
4.11 Binary Search — Problems
4.13 Trees
4.14 Tree — Problems
4.15 Trie — Problems
4.17 Heap — Problems
4.18 Backtracking — Problems
4.19 Graphs
4.20 Graph — Problems
4.21 Advanced Graph — Problems
4.23 1-D DP — Problems
4.24 2-D DP — Problems
4.26 Greedy — Problems
4.27 Interval — Problems
4.28 Math & Geometry — Problems
4.30 Bit Manipulation — Problems
Part 5 — Networking & the Web
5.3 IP
5.4 Transport
5.6 HTTP
Part 6 — Frontend Engineering
6.1 Browser Internals
6.2 HTML & CSS Mastery
6.3 JavaScript in the Browser
6.4 React, from First Component to Full Shop
6.5 Frameworks & Rendering
6.8 UI Engineering & Patterns
Part 7 — Databases & Storage
7.2 SQL Mastery
7.3 Storage Engine Internals
7.4 Transactions
7.5 NoSQL Taxonomy
7.8 Analytics & Big Data
Part 8 — Security, Identity & Cryptography
8.2 Cryptography
8.3 Protocols of Trust
8.4 Identity: AuthN & AuthZ
8.5 Application Security
8.6 Infrastructure Security
Part 9 — Software Design (LLD)
9.2 OOP Foundations
9.3 Design Principles
9.4 Design Patterns
9.5 Concurrency
9.6 API Design
9.7 LLD Interview Machines
9.9 Node/Express Production Playbook
Part 10 — Distributed Systems & HLD
10.7 Consistency & Consensus
10.8 Messaging & Microservices
10.14 Caching
Building blocks from the design seat
Part 11 — System Design Case Studies
Part 12 — AI & ML Engineering
12.1 What AI Engineering Is
12.2 The Math You Need
12.3 Classical Machine Learning
12.4 Data for ML
12.5 Deep Learning
12.6 Embeddings & Vector Search
12.7 Transformers & LLMs
12.8 Building with LLMs
12.9 Retrieval-Augmented Generation
12.10 Agents
12.11 Adapting Models
12.12 Production AI
12.13 Multimodal AI
12.14 AI Security & Governance
12.15 Case Studies & Capstone
Part 13 — Cloud, DevOps & Infrastructure
13.11 Git, from First Commit to Team Workflow
Part 14 — Containers: Docker & Kubernetes
14.1 Foundations
14.2 Docker
14.3 Kubernetes
14.4 Kubernetes on Azure
Part 15 — The Craft & Career
Nothing picked yet