LeetCode · #268
Missing Number Solution
Given array of n distinct numbers in [0, n], find the missing one.
01
Section One · Problem
Problem Statement
Example
Input: nums = [3,0,1]
Output: 2 // range [0,3], missing 2
02
Section Two · Approach 1
Sort — O(n log n)
Sort and find where nums[i] != i.
Better: Gauss sum:
expected = n*(n+1)/2, subtract actual sum. Or XOR: XOR [0..n] with all elements — pairs cancel, missing remains.03
Section Three · Approach 2
Sum Formula or XOR — O(n), O(1)
Sum: n*(n+1)/2 - sum(nums). XOR: XOR all indices [0..n] with all elements. Duplicates cancel, missing remains.
💡 Mental model (sum): You know the sum of a complete set. The actual sum is less — the difference is the missing piece. Like counting money: expected $55, got $53, missing $2.
💡 XOR variant: XOR index 0 with nums[0], index 1 with nums[1], ..., index n (the extra index) with nothing. All present numbers pair up (index ⊕ value), leaving the missing one.
04
Section Four · Trace
Visual Walkthrough
Missing Number — Sum Formula
05
Section Five · Implementation
Code — Java & Python
Java — XOR
class Solution {
public int missingNumber(int[] nums) {
int xor = nums.length;
for (int i = 0; i < nums.length; i++)
xor ^= i ^ nums[i];
return xor;
}
}
Python — Sum formula
class Solution:
def missingNumber(self, nums: list[int]) -> int:
n = len(nums)
return n * (n + 1) // 2 - sum(nums)
06
Section Six · Analysis
Complexity Analysis
| Approach | Time | Space |
|---|---|---|
| Sort | O(n log n) | O(1) |
| HashSet | O(n) | O(n) |
| Sum / XOR ← optimal | O(n) | O(1) |
07
Section Seven · Edge Cases
Edge Cases & Pitfalls
| Case | Input | Why It Matters |
|---|---|---|
| Missing 0 | [1] | expected=1, actual=1… wait, n=1, expected=1 → 1-1=0. Missing 0. |
| Missing n | [0,1,2] | n=3, expected=6, actual=3, missing=3. |
| Single element | [0] | Missing 1. n=1, 1-0=1. |
⚠ Common Mistake: Sum formula can overflow for very large n with 32-bit ints. Use
long or XOR (no overflow risk). Python has arbitrary precision so no issue there.