Find the Missing Number
Mahabharata — The Absent Warrior — Which Soldier from 0 to n Failed to Report
शतेषु योधेषु एको नास्ति — कः अनुपस्थितः?। संख्यां गणयित्वा अभावं जानीहि — स एव लुप्तः॥
*Among a hundred warriors, one is absent — who is missing? Count the numbers, find the void — that is the lost one.*
The Story
An array contains n distinct numbers from the range [0, n]. Exactly one number is missing. Find it.
Two approaches, both O(n) time O(1) space:
**Approach 1 — Math (Sum):** Expected sum of 0 to n = n*(n+1)/2. Actual sum = array sum. Missing = Expected - Actual.
For `nums = [3,0,1]` (n=3): Expected = 3*4/2 = 6. Actual = 4. Missing = 2. ✓
**Approach 2 — Cyclic Sort:** Modify cyclic sort for 0..n: number x belongs at index x. After sorting, find the index where nums[i] ≠ i.
For `nums = [3,0,1]`: - i=0: nums[0]=3, correct=3. swap → [1,0,3] wait... nums[3] doesn't exist! n=3, indices 0..2 only. - Handle: if nums[i] == n (the extra number), skip (i++). Otherwise swap. After sort: [0,1,3] (or [0,1,2] with 3 at index 2... let's trace carefully) - i=0: 3 == n(3) → i++ - i=1: 0, correct=0. swap with index 0 → [0,3,1] → i stays 0 - Actually let me redo:
nums=[3,0,1], n=3 - i=0: nums[0]=3==n → i++ - i=1: nums[1]=0, correct=0. 0≠1 → swap → [0,3,1]. i stays 1 - i=1: nums[1]=3==n → i++ - i=2: nums[2]=1, correct=1. 2≠1 → swap → [0,1,3]. i stays 2 - i=2: nums[2]=3==n → i++ After: [0,1,3]. Check: nums[0]=0✓, nums[1]=1✓, nums[2]=3≠2 → missing=2 ✓
The math approach is simpler for this problem. The cyclic sort approach generalizes to cs-3.
The Roll-Call's First Instinct
Sort the array. Scan for the first index where nums[i] ≠ i. O(n log n).
public int missingNumberBruteForce(int[] nums) {
Arrays.sort(nums);
for (int i = 0; i < nums.length; i++)
if (nums[i] != i) return i;
return nums.length; // missing is n
}The Mathematician's Wisdom
public int missingNumber(int[] nums) {
int n = nums.length;
int expected = n * (n + 1) / 2;
int actual = 0;
for (int x : nums) actual += x;
return expected - actual;
}Step-by-Step Walkthrough
nums=[0,1] n=2. Expected=3. Actual=1. Missing=2 ✅ nums=[1] n=1. Expected=1. Actual=1. Missing=0 ✅
Deep Insight
**Why cyclic sort for 0..n range?** Element x goes to index x. After sort, any index i where nums[i] ≠ i is the missing number. If all n indices check out, the missing number is n itself.
**Math approach overflow concern:** For large n, use XOR or long. XOR approach: `n ^ (n-1) ^ ... ^ 0 ^ nums[0] ^ ... ^ nums[n-1]` = missing number. XOR of all numbers twice = 0, XOR with missing once = missing.
**Cyclic sort generalizes better:** For cs-3 (multiple missing numbers), cyclic sort extends naturally while math sum doesn't.
Complexity Analysis
| Approach | Time | Space | Note |
|---|---|---|---|
| Brute Force | O(n log n) | O(1) | Sort then scan |
| Optimal | O(n) | O(1) | Single pass sum computation |
Pattern Recognition
✅ Find missing number in 0..n ✅ Math: n*(n+1)/2 - sum(array) ✅ Or cyclic sort: x belongs at index x; find mismatch ✅ Both O(n) time, O(1) space **LeetCode Trigger Phrases:** → "missing number in 0..n" → "exactly one number missing" + consecutive range → "find the absent element"
Bhagavad Gita 2.23
नैनं छिन्दन्ति शस्त्राणि नैनं दहति पावकः। न चैनं क्लेदयन्त्यापो न शोषयति मारुतः॥
The soul can never be cut by any weapon, nor burned by fire, nor moistened by water, nor dried by the wind.
Connection: The missing warrior cannot truly be destroyed — their absence is felt in the very sum of what remains. The algorithm doesn't search through every possibility; it calculates the void from what exists. Like the imperishable soul whose absence from the physical realm leaves a mathematical trace in the universe's accounting, the missing number is revealed by the gap between what should be and what is.