Approach Summary
XOR of all indices (0..n) XOR all array values. The missing number is what remains. Or use Gauss sum formula.
Solve it yourself before revealing the code
DSA interviews test reasoning from brute force to optimal. Think through the constraints first.
Solution Progression (Brute Force → Most Optimized)
Understand the architectural evolution from naive baseline to optimal complexity.
| Approach | Time | Space | Core Strategy / Trade-off |
|---|---|---|---|
| 1 Approach 1: Gauss Sum Formula (Arithmetic Series) | O(n) | O(1) | Compute expected sum n * (n + 1) / 2 and subtract the sum of elements in nums. |
| 2 Approach 2: Bitwise XOR Cancellation (Optimal Bit Manipulation) | O(n) | O(1) | XOR all numbers from 0 to n with all elements in nums to cancel duplicates in O(1) space. |
Approach 1: Gauss Sum Formula (Arithmetic Series)
The sum of the first n natural numbers is given by n * (n + 1) / 2. By summing all numbers in the input array and subtracting that total from the expected sum, the remaining difference is exactly the missing number. This approach is intuitive and fast, though care must be taken with 32-bit signed integer limits for very large n.
Approach 1: Gauss Sum Formula (Arithmetic Series) Implementation
Approach 1: Gauss Sum Formula (Arithmetic Series)
class Solution {
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;
}
}class Solution {
public:
int missingNumber(vector<int>& nums) {
int n = nums.size();
long long expected = (long long)n * (n + 1) / 2;
long long actual = 0;
for (int x : nums) {
actual += x;
}
return expected - actual;
}
};class Solution:
def missingNumber(self, nums: list[int]) -> int:
n = len(nums)
expected = n * (n + 1) // 2
actual = sum(nums)
return expected - actualfunction missingNumber(nums) {
const n = nums.length;
const expected = (n * (n + 1)) / 2;
const actual = nums.reduce((acc, x) => acc + x, 0);
return expected - actual;
}Approach 2: Bitwise XOR Cancellation (Optimal Bit Manipulation)
Because XOR is commutative and associative, and x ^ x = 0 while x ^ 0 = x, pairing each index i with array element nums[i] will cancel every number that is present. Initialize xorSum = n (the last index), then iterate i from 0 to n - 1 and XOR xorSum ^= i ^ nums[i]. All numbers present in both ranges annihilate each other, leaving only the unique unmatched missing number with zero risk of arithmetic overflow.
Approach 2: Bitwise XOR Cancellation (Optimal Bit Manipulation) Implementation
Approach 2: Bitwise XOR Cancellation (Optimal Bit Manipulation)
class Solution {
public int missingNumber(int[] nums) {
int xorSum = nums.length;
for (int i = 0; i < nums.length; i++) {
xorSum ^= i ^ nums[i];
}
return xorSum;
}
}class Solution {
public:
int missingNumber(vector<int>& nums) {
int xorSum = nums.size();
for (int i = 0; i < nums.size(); i++) {
xorSum ^= i ^ nums[i];
}
return xorSum;
}
};class Solution:
def missingNumber(self, nums: list[int]) -> int:
xor_sum = len(nums)
for i, val in enumerate(nums):
xor_sum ^= i ^ val
return xor_sumfunction missingNumber(nums) {
let xorSum = nums.length;
for (let i = 0; i < nums.length; i++) {
xorSum ^= i ^ nums[i];
}
return xorSum;
}Edge Cases to Watch
- Missing number is 0 (array contains [1..n])
- Missing number is n (array contains [0..n-1])
- Array has length 1 (e.g. [0] -> missing 1, [1] -> missing 0)
- Large array with up to 10^4 numbers
Master the Bit Manipulation Pattern
Study the core invariant, step-by-step decision framework, and common interview traps for the Bit Manipulation pattern.
How to Recognize This Pattern
- Find missing number in 0..n
- XOR or math sum
Complexity Analysis
Time Complexity
O(n)
Space Complexity
O(1)