80. Missing Number
🔗 LeetCode Problem: 268. Missing Number
📊 Difficulty: Easy
🏷️ Topics: Array, Hash Table, Math, Binary Search, Bit Manipulation, Sorting
Problem Statement
Given an array nums containing n distinct numbers in the range [0, n], return the only number in the range that is missing from the array.
Example 1:
Input: nums = [3,0,1]
Output: 2
Explanation:
n = 3 since there are 3 numbers
Range is [0, 1, 2, 3]
Numbers present: 0, 1, 3
Missing: 2
Example 2:
Input: nums = [0,1]
Output: 2
Explanation:
n = 2 since there are 2 numbers
Range is [0, 1, 2]
Numbers present: 0, 1
Missing: 2
Example 3:
Input: nums = [9,6,4,2,3,5,7,0,1]
Output: 8
Explanation:
n = 9 since there are 9 numbers
Range is [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
Missing: 8
Constraints:
- n == nums.length
- 1 <= n <= 10^4
- 0 <= nums[i] <= n
- All the numbers of nums are unique.
Follow up: Could you implement a solution using only O(1) extra space complexity and O(n) runtime complexity?
🌟 ELI5: The Simple Idea!
Think of it like a classroom attendance:
You have a class with students numbered 0 to 10
Total: 11 students (0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10)
Students present: [0, 1, 2, 4, 5, 6, 7, 8, 9, 10]
Who's absent? Student #3!
That's the missing number! ✓
The Key Insight:
If you have n numbers in the array,
you should have numbers from 0 to n.
Example: 3 numbers in array
Should have: 0, 1, 2, 3 (that's 4 total possibilities)
Actually have: 3 numbers
Missing: 1 number
The range is always [0, n] where n = array length!
Visual Example:
Array: [3, 0, 1]
Length: 3
Expected: 0, 1, 2, 3 (4 numbers for range [0,3])
Present: 0, 1, 3 (only 3 numbers in array)
Missing: 2 ✓
It's like having 4 parking spots (0,1,2,3)
but only 3 cars!
Which spot is empty? Spot 2!
🎨 Visual Understanding
The Problem Visualized
Example 1: nums = [3, 0, 1]
Parking Spots (indices): 0 1 2 3
Expected Numbers: 0 1 2 3
↓ ↓ ↓ ↓
What we have: 0 1 ? 3
↑
Missing!
The array has 3 elements, so we expect 0-3 (4 numbers)
We have: 0, 1, 3
Missing: 2 ✓
Example 2: nums = [9,6,4,2,3,5,7,0,1]
Length: 9, so range is [0, 9]
Expected: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9
Present: 0, 1, 2, 3, 4, 5, 6, 7, 9
(notice 8 is missing!)
Missing: 8 ✓
The Cyclic Sort Concept
For Cyclic Sort:
Number i should be at index i!
Example: [3, 0, 1]
Perfect placement:
Index: 0 1 2 3
Value: 0 1 2 3
↑ ↑ ↑ ↑
Each number at its own index!
Current placement:
Index: 0 1 2
Value: 3 0 1
After cyclic sort:
Index: 0 1 2
Value: 0 1 3
↓ ↓ ↓
✓ ✓ Wrong! (Should be 2)
Index 2 has wrong value (3 instead of 2)
So 2 is missing! ✓
🎯 Approach 1: HashSet (Simple)
The Most Natural Thinking 💭
Core Logic:
Put all numbers in a set
Check which number from 0 to n is missing
Implementation
/**
* Using HashSet
* Time: O(n), Space: O(n)
*/
public int missingNumber(int[] nums) {
Set<Integer> numSet = new HashSet<>();
// Add all numbers to set
for (int num : nums) {
numSet.add(num);
}
// Check which number from 0 to n is missing
int n = nums.length;
for (int i = 0; i <= n; i++) {
if (!numSet.contains(i)) {
return i; // Found missing number!
}
}
return -1; // Should never reach here
}
⏰ Time: O(n) - Two passes
💾 Space: O(n) - HashSet
❌ Problem: Uses O(n) space! Can we do better?
🎯 Approach 2: Math - Sum Formula ⭐
Better Approach 💡
🧠 The Brilliant Insight
Mathematical approach using sum formula!
Sum of 0 to n = n × (n + 1) / 2
Example: n = 3
Expected sum: 0 + 1 + 2 + 3 = 6
Formula: 3 × 4 / 2 = 6 ✓
If array is [3, 0, 1]:
Actual sum: 3 + 0 + 1 = 4
Expected sum: 6
Missing: 6 - 4 = 2 ✓
Implementation
/**
* Using Sum Formula
* Time: O(n), Space: O(1)
*/
public int missingNumber(int[] nums) {
int n = nums.length;
// Calculate expected sum (0 to n)
int expectedSum = n * (n + 1) / 2;
// Calculate actual sum
int actualSum = 0;
for (int num : nums) {
actualSum += num;
}
// Missing number = difference
return expectedSum - actualSum;
}
⏰ Time: O(n) - Single pass
💾 Space: O(1) - Only variables
✓ Perfect! O(1) space!
🔍 Dry Run
Example: nums = [3, 0, 1]
Step 1: Calculate expected sum
n = 3 (array length)
expectedSum = n × (n + 1) / 2
= 3 × 4 / 2
= 12 / 2
= 6
Step 2: Calculate actual sum
actualSum = 0
Loop through array:
nums[0] = 3: actualSum = 0 + 3 = 3
nums[1] = 0: actualSum = 3 + 0 = 3
nums[2] = 1: actualSum = 3 + 1 = 4
actualSum = 4
Step 3: Find missing
missing = expectedSum - actualSum
= 6 - 4
= 2 ✓
Result: 2
Example 2: nums = [9,6,4,2,3,5,7,0,1]
Step 1: Expected sum
n = 9
expectedSum = 9 × 10 / 2 = 45
Step 2: Actual sum
9+6+4+2+3+5+7+0+1 = 37
Step 3: Missing
45 - 37 = 8 ✓
Result: 8
🎯 Approach 3: XOR (Bit Manipulation) ⭐
Even Smarter! 💡
🧠 The XOR Magic
XOR Properties:
a ⊕ a = 0 (same numbers cancel out)
a ⊕ 0 = a (XOR with 0 gives original)
XOR is commutative and associative
Strategy:
XOR all indices (0 to n) with all array values
All present numbers cancel out
Only missing number remains!
Example: [3, 0, 1]
Indices: 0, 1, 2, 3
Values: 3, 0, 1
XOR chain:
0 ⊕ 1 ⊕ 2 ⊕ 3 ⊕ 3 ⊕ 0 ⊕ 1
= 0 ⊕ 0 ⊕ 1 ⊕ 1 ⊕ 2 ⊕ 3 ⊕ 3
= 2 ✓
All numbers cancel except 2!
Implementation
/**
* Using XOR
* Time: O(n), Space: O(1)
*/
public int missingNumber(int[] nums) {
int result = nums.length; // Start with n
for (int i = 0; i < nums.length; i++) {
result ^= i ^ nums[i]; // XOR index and value
}
return result;
}
⏰ Time: O(n) - Single pass
💾 Space: O(1) - Only one variable
✓ No overflow risk like sum approach!
🔍 XOR Dry Run
Example: nums = [3, 0, 1]
Step 1: Initialize
result = n = 3
Binary: result = 11
Step 2: Loop through array
i = 0, nums[0] = 3:
result ^= 0 ^ 3
Binary: 11 ⊕ 00 ⊕ 11
= 11 ⊕ 11
= 00
result = 0
i = 1, nums[1] = 0:
result ^= 1 ^ 0
Binary: 00 ⊕ 01 ⊕ 00
= 01
result = 1
i = 2, nums[2] = 1:
result ^= 2 ^ 1
Binary: 01 ⊕ 10 ⊕ 01
= 10
result = 2
Result: 2 ✓
Visual of XOR cancellation:
Start: 3
3 ⊕ 0 ⊕ 3 → cancels to 0
0 ⊕ 1 ⊕ 0 → cancels to 1
1 ⊕ 2 ⊕ 1 → cancels to 2
Only 2 remains! ✓
🎯 Approach 4: Cyclic Sort (Pattern Practice)
Cyclic Sort Approach 💡
🧠 The Cyclic Sort Way
Place each number at its correct index
Number i should be at index i
After sorting:
Check each index
If nums[i] != i, then i is missing
If all match, then n is missing!
Implementation
/**
* Using Cyclic Sort
* Time: O(n), Space: O(1)
*/
public int missingNumber(int[] nums) {
int i = 0;
int n = nums.length;
// Cyclic sort: place each number at correct index
while (i < n) {
int correctIndex = nums[i];
// If number is in range [0, n-1] and not at correct position
if (nums[i] < n && nums[i] != nums[correctIndex]) {
swap(nums, i, correctIndex);
} else {
i++;
}
}
// Find which index has wrong number
for (i = 0; i < n; i++) {
if (nums[i] != i) {
return i; // This index value is missing
}
}
// If all indices 0 to n-1 are correct, then n is missing
return n;
}
private void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
⏰ Time: O(n) - Each number swaps at most once
💾 Space: O(1) - In-place sorting
🔍 Cyclic Sort Dry Run
Example: nums = [3, 0, 1]
Goal: Place each number at its index
Initial: [3, 0, 1]
Index: 0 1 2
═══════════════════════════════════════════════════════════════
Cyclic Sort Phase
═══════════════════════════════════════════════════════════════
i = 0:
nums[0] = 3
correctIndex = 3
Is 3 in range [0, n-1]? [0, 2]? No (3 >= n)
Can't place 3 at index 3 (doesn't exist!)
i++
Array: [3, 0, 1]
i = 1:
nums[1] = 0
correctIndex = 0
Is nums[1] at correct position? 0 != nums[0](3)? Yes, swap
Swap nums[1] with nums[0]
Array: [0, 3, 1]
i stays at 1
i = 1 (again):
nums[1] = 3
correctIndex = 3
3 >= n, skip
i++
Array: [0, 3, 1]
i = 2:
nums[2] = 1
correctIndex = 1
Is nums[2] at correct position? 1 != nums[1](3)? Yes, swap
Swap nums[2] with nums[1]
Array: [0, 1, 3]
i stays at 2
i = 2 (again):
nums[2] = 3
3 >= n, skip
i++
i = 3, exit while loop
Final array: [0, 1, 3]
═══════════════════════════════════════════════════════════════
Find Missing Phase
═══════════════════════════════════════════════════════════════
Check each index:
i = 0: nums[0] = 0, expected 0 ✓
i = 1: nums[1] = 1, expected 1 ✓
i = 2: nums[2] = 3, expected 2 ✗
Index 2 has wrong value!
Return 2 ✓
Example 2: nums = [0, 1]
Initial: [0, 1]
Cyclic Sort:
i = 0: nums[0] = 0, already at index 0 ✓
i = 1: nums[1] = 1, already at index 1 ✓
Final: [0, 1]
Find Missing:
i = 0: nums[0] = 0 ✓
i = 1: nums[1] = 1 ✓
All correct! So n = 2 is missing!
Return 2 ✓
🎯 Comparison of All Approaches
Approach Time Space Notes
═══════════════════════════════════════════════════════════════
HashSet O(n) O(n) Simple, uses extra space
Sum Formula O(n) O(1) Best! Risk of overflow
XOR O(n) O(1) Best! No overflow risk
Cyclic Sort O(n) O(1) Good for pattern practice
Recommended for Interview: Sum Formula or XOR
Recommended for Practice: Cyclic Sort (pattern mastery)
Which to Use When?
Use Sum Formula when: - ✓ Numbers are small (no overflow) - ✓ Want clearest solution - ✓ Interviewer asks for mathematical approach
Use XOR when: - ✓ Worried about overflow - ✓ Want to show bit manipulation skills - ✓ Interviewer likes clever solutions
Use Cyclic Sort when: - ✓ Practicing the pattern - ✓ Follow-up asks for in-place sorting - ✓ Want to demonstrate versatility
🎯 Why Sum Formula Works - Proof
The Mathematical Insight:
═══════════════════════════════════════════════════════════════
Sum of first n natural numbers: 1 + 2 + ... + n = n(n+1)/2
For 0 to n: 0 + 1 + 2 + ... + n = n(n+1)/2
Proof by example:
n = 4: 0+1+2+3+4 = 10
Formula: 4 × 5 / 2 = 10 ✓
n = 100: 0+1+...+100 = 5050
Formula: 100 × 101 / 2 = 5050 ✓
Why missing = expected - actual:
If all numbers present: actual = expected
If one missing: actual = expected - missing
Therefore: missing = expected - actual ✓
Example:
Expected: 0+1+2+3 = 6
Actual: 0+1+3 = 4
Missing: 6-4 = 2 ✓
Overflow Consideration
// Potential overflow for large n
int expectedSum = n * (n + 1) / 2; // n*n could overflow!
// Safer alternative using long
long expectedSum = (long) n * (n + 1) / 2;
// Or use XOR (no overflow possible!)
🎯 Why XOR Works - Deep Dive
XOR Truth Table:
0 ⊕ 0 = 0
0 ⊕ 1 = 1
1 ⊕ 0 = 1
1 ⊕ 1 = 0
Key Properties:
a ⊕ a = 0 (cancellation)
a ⊕ 0 = a (identity)
a ⊕ b ⊕ a = b (order doesn't matter)
Application to Missing Number:
═══════════════════════════════════════════════════════════════
Array: [3, 0, 1]
XOR all indices AND values:
result = 0 ⊕ 1 ⊕ 2 ⊕ 3 ⊕ 3 ⊕ 0 ⊕ 1
↑ ↑ ↑ ↑ ↑ ↑ ↑
indices values
Rearrange (XOR is commutative):
= 0 ⊕ 0 ⊕ 1 ⊕ 1 ⊕ 3 ⊕ 3 ⊕ 2
↓───↓ ↓───↓ ↓───↓ ↓
= 0 = 0 = 0 = 2
All pairs cancel, only 2 remains! ✓
Why This Works:
- Every number from 0 to n appears in indices
- Every number except missing appears in values
- When we XOR all together, pairs cancel
- Only the missing number (from indices) has no pair
- It survives! ✓
⚠️ Common Mistakes to Avoid
Mistake 1: Wrong sum formula
// ❌ WRONG - Missing the 0
int expectedSum = n * (n + 1) / 2; // This is actually correct!
// Common mistake is forgetting it includes 0
// Range is [0, n], not [1, n]!
Mistake 2: Overflow in sum
// ❌ WRONG - Might overflow for large n
int expectedSum = n * (n + 1) / 2;
// ✓ CORRECT - Use long
long expectedSum = (long) n * (n + 1) / 2;
Mistake 3: XOR initialization
// ❌ WRONG - Start from 0
int result = 0;
for (int i = 0; i <= n; i++) {
result ^= i;
}
// Missing one XOR with n!
// ✓ CORRECT - Start with n
int result = n;
for (int i = 0; i < n; i++) {
result ^= i ^ nums[i];
}
Mistake 4: Cyclic sort boundary
// ❌ WRONG - Tries to place n
if (nums[i] != nums[correctIndex]) {
swap(...);
}
// Will crash when nums[i] = n!
// ✓ CORRECT - Check range first
if (nums[i] < n && nums[i] != nums[correctIndex]) {
swap(...);
}
🎯 Pattern Recognition
Problem Type: Find Missing Number in Range
Core Pattern: Multiple approaches available
When to Apply:
✓ Array has n elements
✓ Values in range [0, n]
✓ Exactly one number missing
✓ All numbers unique
Recognition Keywords:
- "Missing number"
- "Range [0, n]"
- "n distinct numbers"
- "One number missing"
Similar Problems:
- Find Disappeared Numbers (LC 448) - Multiple missing
- First Missing Positive (LC 41) - Different range
- Find Duplicate (LC 287) - Opposite problem
Best Approach for Interview:
┌────────────────────────────────────────────┐
│ Sum Formula: Most intuitive │
│ XOR: If worried about overflow │
│ Cyclic Sort: For pattern demonstration │
│ All are O(n) time, O(1) space ✓ │
└────────────────────────────────────────────┘
🧠 Interview Strategy
Step 1: "I see several approaches"
Step 2: "Sum formula is most intuitive"
Step 3: "XOR avoids overflow"
Step 4: "Cyclic sort also works"
Step 5: "I'll use sum formula - O(n) time, O(1) space"
Key Points to Mention:
- Multiple valid O(1) space solutions
- Sum formula: expectedSum - actualSum
- Formula: n(n+1)/2 for sum 0 to n
- XOR approach if overflow is concern
- Cyclic sort for pattern demonstration
- All achieve O(n) time, O(1) space
Why Sum Formula?
"The sum of 0 to n is n(n+1)/2 by the arithmetic series formula.
If I calculate the expected sum and subtract the actual sum of
the array, the difference is the missing number. This is O(n)
time for one pass through the array, and O(1) space using only
a couple variables. If overflow is a concern with large numbers,
I can use XOR instead, which has the same complexity but no
overflow risk."
Edge Cases to Mention:
✓ Missing number is 0
✓ Missing number is n (largest)
✓ Array has 1 element
✓ Large n (overflow consideration)
📝 Quick Revision Notes
🎯 Core Concept:
Missing Number: Array has n numbers in range [0, n]. Three O(1) space approaches: Sum formula (expected - actual), XOR (pairs cancel), Cyclic sort (place i at index i). Formula: n(n+1)/2. All O(n) time, O(1) space!
⚡ Quick Implementation (Sum):
public int missingNumber(int[] nums) {
int n = nums.length;
int expected = n * (n + 1) / 2;
int actual = 0;
for (int num : nums) actual += num;
return expected - actual;
}
⚡ Quick Implementation (XOR):
class Test {
public int missingNumber(int[] a) {
int len = a.length;
// // Approach 1 - XOR
// int xor = 0;
// for(int i = 1; i <= len; i++) {
// xor = xor ^ i ^ a[i - 1];
// }
// return xor;
// Approach 2 - cyclic sort.
int i = 0;
while (i < len) {
if(a[i] < len && i != a[i]) {
swap(a, i, a[i]);
} else {
i++;
}
}
for(i = 0; i < len; i++) {
if(i != a[i]) {
return i;
}
}
return len;
}
private void swap(int[] a, int i, int j) {
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
public static void main(String[] args) {
Test t = new Test();
System.out.println(t.missingNumber(new int[] {3, 0, 1}) == 2);
System.out.println(t.missingNumber(new int[] {0}) == 1);
System.out.println(t.missingNumber(new int[] {1}) == 0);
System.out.println(t.missingNumber(new int[] {0, 1}) == 2);
System.out.println(t.missingNumber(new int[] {0, 1, 3}) == 2);
System.out.println(t.missingNumber(new int[] {9,6,4,2,3,5,7,0,1}) == 8);
}
}
🔑 Key Insights:
- Pattern: Multiple elegant solutions!
- Sum: n(n+1)/2 - actualSum
- XOR: All pairs cancel, missing remains
- Cyclic: Place i at index i, find mismatch
- Range: [0, n] with n elements → 1 missing
- Time: O(n), Space: O(1) (all approaches)
🎪 Memory Aid:
"Expected minus actual equals missing!"
"XOR pairs cancel, orphan remains!"
Think: "3 ways, all O(1) space!" ✨
💡 The Key Formulas:
Sum Formula:
expectedSum = n × (n + 1) / 2
missing = expectedSum - actualSum
XOR Magic:
result = n
result ^= each (index ^ value)
All pairs cancel!
Cyclic Sort:
Place i at index i
Check where nums[i] != i
🧪 Edge Cases
Case 1: Missing 0
Input: nums = [1]
Output: 0
(Range [0,1], missing 0)
Case 2: Missing n
Input: nums = [0,1]
Output: 2
(Range [0,2], missing 2)
Case 3: Missing middle
Input: nums = [0,1,3]
Output: 2
Case 4: Single element
Input: nums = [0]
Output: 1
Input: nums = [1]
Output: 0
All handled correctly by all approaches! ✓
Related Patterns
- Find All Disappeared Numbers (LC 448) - Multiple missing
- First Missing Positive (LC 41) - Range [1, n]
- Single Number (LC 136) - XOR technique
- Find Duplicate (LC 287) - Opposite problem
Happy practicing! 🎯
Note: This problem is PERFECT for demonstrating multiple solution approaches in an interview! You can start with the simple HashSet, then impress with the O(1) space solutions. The sum formula is most intuitive, XOR shows algorithmic thinking, and Cyclic Sort demonstrates pattern mastery! Choose based on the interview context! 💪✨