Skip to content

Volume ITechnology

4.30.5 — Missing Number ​

LeetCode 268 · Easy · ★ Blind 75

The problem ​

An array holds n distinct numbers taken from the range 0 to n. Exactly one is missing. Find it.

[3,0,1]           →  2
[9,6,4,2,3,5,7,0,1]  →  8
[0]               →  1

The follow-up asks for O(n) time and O(1) extra space.

Three solutions ​

All three are O(n); the difference is space and overflow behaviour.

Sorting is O(n \log n) and immediately out.

A hash set is O(n) time and O(n) space — fails the follow-up.

Two real answers remain.

Solution 1 — the sum formula ​

The numbers 0 to n sum to a known value, thanks to Gauss:

0 + 1 + \cdots + n = \frac{n(n+1)}{2}

Subtract the actual sum and the difference is the missing number.

python
n = len(nums)
return n * (n + 1) // 2 - sum(nums)

One line, and easy to explain.

The catch is overflow. For very large n, the expected sum can exceed a fixed-width integer even when the answer does not. In Python integers are unbounded, so it cannot happen; in Java or C++ it can, and the standard fix is to subtract as you go rather than computing both totals first:

python
missing = n
for i, x in enumerate(nums):
    missing += i - x
return missing

That keeps every intermediate value small, and it is what you would write in a fixed-width language.

Solution 2 — XOR ​

XOR every index together with every value.

Each number from 0 to n appears twice — once as an index and once as a value — except the missing one, which appears only as an index. Every pair cancels, and the missing number survives.

No overflow is possible, because XOR never produces a bit outside the range of its inputs. That is its advantage over the sum formula, and it is the reason to prefer it.

The solution ​

python
class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        result = len(nums)                    # (1) the index n has no array slot

        for i, x in enumerate(nums):  # (2)
            result ^= i ^ x  # (3)

        return result  # (4)
ts
function missingNumber(nums: number[]): number {
  let result = nums.length;  // (1)

  for (let i = 0; i < nums.length; i++) {  // (2)
    result ^= i ^ nums[i];  // (3)
  }

  return result;  // (4)
}

Line by line ​

The list holds n different numbers from 0 to n, so exactly one is missing. Its positions run from 0 to n − 1.

(1) Start with n. The numbers 0 to n should all appear. The positions supply 0 to n − 1, so n itself must be added by hand.

(2) Go through every position i and its value x.

(3) XOR in both the position and the value. Every number from 0 to n that is present appears twice in total, once as a position (or as the starting n) and once as a value, so it cancels out, as in 4.30.1. The missing number appears only once, as a position or as n, so it is left over.

(4) The missing number.

Trace ​

Take [3, 0, 1], so n = 3.

Stepixresult
start3
1033 ^ 0 ^ 3 = 0
2100 ^ 1 ^ 0 = 1
3211 ^ 2 ^ 1 = 2

The answer is 2.

result starts at len(nums), which is n. The indices only run from 0 to n−1, so n itself would never be XOR-ed in otherwise — and n is a legitimate candidate for the missing number, as [0] shows.

result ^= i ^ x folds both the index and the value in on each iteration.

Trace ​

[3, 0, 1], so n = 3.

Start at 3. Then XOR in 0^3, 1^0, 2^1.

Everything together: 3 ^ 0 ^ 3 ^ 1 ^ 0 ^ 2 ^ 1. Reorder: (3^3) ^ (0^0) ^ (1^1) ^ 2 = 2 ✓.

The reordering is legal because XOR is commutative — which is why the array's order never matters.

Edge cases ​

  • The missing number is n, like [0, 1]. Only the starting n is unmatched, so the answer is 2.
  • The missing number is 0, like [1]. Position 0 is unmatched, so the answer is 0.

Complexity ​

O(n) time, O(1) space, for both real solutions.

Which to write ​

Say the sum formula first — it is the most natural and easiest to explain — then mention that XOR avoids overflow entirely. Offering both plus the trade is a better answer than either alone.

Where this goes next ​

  • Single Number — XOR cancelling pairs, the same property. 4.30.1.
  • Find All Numbers Disappeared in an Array — several missing, so XOR cannot separate them. Mark visited by negating nums[abs(x) - 1], then report the indices still positive. A good demonstration of when XOR stops working.
  • Find the Duplicate Number — one duplicate, no mutation, no extra space. XOR does not help; it becomes cycle detection. 4.9.8.
  • Set Mismatch — one number duplicated and one missing. Both the sum and XOR approaches extend, and the XOR version needs the partition-by-a-differing-bit trick from 4.30.1.

The pattern across all of these: when values and indices come from the same range, pair them off and see what survives.

What the interviewer will push on ​

"Why does XOR work here?" Every number appears twice — once as an index, once as a value — except the missing one.

"Why start at n?" The indices stop at n−1, so n must be introduced by hand.

"Why prefer XOR over the sum?" No overflow. Then note that Python makes the point moot but the habit is right.

"What if several numbers were missing?" XOR cannot separate them. Use the negation-marking trick or a set.

"What is the sum formula?" n(n+1)/2, and say Gauss's name if you like the story.

One thing to volunteer: give both solutions and the overflow trade in one breath. This is an easy problem, and the way to stand out on it is to show you thought about the failure mode rather than just the answer.

Next: 4.30.6 Sum of Two Integers — addition without +, and the Python trap that makes it genuinely awkward.

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