EasyNeetCode150ArrayHash TableMathBit Manipulation
Missing Number
Find missing number in [0,n].
Examples
Input
nums = [3,0,1]
Output
2
Missing 2.
Constraints
- •
n == nums.length - •
0 <= nums[i] <= n - •
Exactly one missing
Approaches
Check 0 to n.
CodeT: O(n) | S: O(n) set
XOR all indices and values.
CodeT: O(n) | S: O(1)
n*(n+1)/2 - sum(nums).
CodeT: O(n) | S: O(1)
def missingNumber(nums):
return len(nums)*(len(nums)+1)//2-sum(nums)Complexity Comparison
| Approach | Time | Space | Description |
|---|---|---|---|
| Hash Set | O(n) | O(n) set | Check 0 to n. |
| XOR | O(n) | O(1) | XOR all indices and values. |
| Math Sum Formula | O(n) | O(1) | n*(n+1)/2 - sum(nums). |
Hash Set
T: O(n)S: O(n) set
Check 0 to n.
XOR
T: O(n)S: O(1)
XOR all indices and values.
Math Sum Formula
T: O(n)S: O(1)
n*(n+1)/2 - sum(nums).
Common Mistakes
Using multiplication (overflow risk)
Wrong formula
Not handling n=0