Bit Manipulation — Missing Number
↗ LeetCode: Missing Number · Easy · pattern chapter →
Asked atMetaAmazonGoogleMicrosoftBloomberg
Given nums containing n distinct integers in [0, n], return the missing one.
Example 1 — nums=[3,0,1] → 2Example 2 — nums=[0,1] → 2Example 3 — nums=[9,6,4,2,3,5,7,0,1] → 8
Constraints — 1 ≤ n ≤ 10⁴. Brute sort + scan is O(n log n) = ~10⁵ ops, sub-millisec but allocates O(1) sort buffer per call. XOR of [0..n] with the array is O(n) = 10⁴ ops with O(1) space and no allocations — ~10⁶ ops/sec throughput on hot infra.
Progressive Hints
Try to solve it yourself first. Reveal hints only when stuck — each hint is progressively more specific.
Interview timer00:00
Practice under interview pressure. Start when you begin reading; stop when you finish. Save best only when you had a full working solution.
Target for interview: Medium = 20-25 min · Hard = 30-40 min · Best time persists on this device only.
Approach 1 — Sort, find gap
O(n log n). Baseline.
Approach 2 — Hash set
O(n) time and O(n) space.
Approach 3 — Gauss sum
missing = n(n+1)/2 - Σ nums.
Approach 4 — XOR fold (canonical)
Insight. XOR 0..n with all of nums. Every present index cancels with its value → missing survives.
java
int missingNumber(int[] nums) {
int x = nums.length;
for (int i = 0; i < nums.length; i++) x ^= i ^ nums[i];
return x;
}Execution Trace
Step 1 / 3Initialize scan.
Complexity — Time O(n); Space O(1).
Try it yourself
Complexity summary
| Approach | Time | Space | Grade |
|---|---|---|---|
| Sort | O(n log n) | O(1) | baseline |
| Hash | O(n) | O(n) | works |
| Gauss sum | O(n) | O(1) | risk overflow |
| XOR fold | O(n) | O(1) | canonical, no overflow |
When to use which
- Standard → XOR fold.
- "Multiple missing" → set difference or sort.
- "Overflow-sensitive" → XOR beats sum.
AI Study CompanionBeta
Related problems
Was this page helpful?
📚 Related problems