Introduction
LeetCode 268: Missing Number is a classic problem that asks you to find the missing number from a range of 0 to n given an array containing n distinct numbers from that range.
It’s a staple question in coding interviews due to its multiple elegant solutions using math, XOR, or 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.
Examples
python
Input: nums = [3, 0, 1]
Output: 2
Input: nums = [0, 1]
Output: 2
Input: nums = [9,6,4,2,3,5,7,0,1]
Output: 8
✅ Step-by-Step Solutions in Python
There are multiple approaches to solve this. Let's explore the top three:
✅ Method 1: Math (Gauss Formula)
We know the sum of first n numbers is:
ini
expected_sum = n * (n + 1) // 2
Subtract the sum of the given array from it.
Python Code:
python
def missingNumber(nums: list[int]) -> int:
n = len(nums)
expected = n * (n + 1) // 2
actual = sum(nums)
return expected - actual
🟢 Time: O(n)
🟢 Space: O(1)
✅ Method 2: XOR Trick
XOR all numbers from 0 to n and all elements in the array. The missing number will remain.
Python Code:
python
def missingNumber(nums: list[int]) -> int:
xor = 0
n = len(nums)
for i in range(n + 1):
xor ^= i
for num in nums:
xor ^= num
return xor
🧠 Why it works:
- XOR cancels out identical numbers:
a ^ a = 0
- Remaining value is the missing one
🟢 Time: O(n)
🟢 Space: O(1)
✅ Method 3: Sort and Compare
Sort the array and compare each index with the value.
python
def missingNumber(nums: list[int]) -> int:
nums.sort()
for i in range(len(nums)):
if nums[i] != i:
return i
return len(nums)
🔴 Time: O(n log n) (due to sort)
🟢 Space: O(1) if sort is in-place
🧪 Dry Run: Input [3, 0, 1]
Expected sum = 3 * 4 / 2 = 6
Actual sum = 3 + 0 + 1 = 4
Missing = 6 - 4 = 2
OR
XOR from 0 to 3: 0 ^ 1 ^ 2 ^ 3 = 0
XOR of array: 3 ^ 0 ^ 1 = 2
0 ^ 2 = 2 ← Missing number ✅
⏱️ Time and Space Complexity Summary
MethodTime ComplexitySpace ComplexityMath (Gauss)O(n)O(1)XOR TrickO(n)O(1)SortingO(n log n)O(1) or O(n)
✅ Conclusion
LeetCode 268: Missing Number is an elegant problem that teaches you multiple techniques:
- Using math to reduce iteration
- Applying bitwise XOR for clever elimination
- Using sorting for brute-force verification