Missing Number
Solve this Problemnums contains n distinct numbers, each drawn from the range [0, n] — so exactly one value in that range is missing from the array. Find it.
Summing 0 through n and subtracting the array's actual sum gets there directly, though the expected-sum formula can overflow for large n before it's ever halved. XOR sidesteps that entirely: XOR together every number from 0 to n with every value actually in the array, and every number that appears in both cancels itself out — the only one left standing is the missing value.
Test Case 1:
Test Case 2:
Test Case 3:
Constraints
- ◆
n == nums.length - ◆
1 ≤ n ≤ 10⁵ - ◆
0 ≤ nums[i] ≤ n - ◆
All the numbers in nums are unique
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Sum Formula
GoodThe numbers 0 through n sum to a fixed total, n(n + 1) / 2. Subtract the array's actual sum from that expected total, and whatever's left over is the missing value. This works, though the expected-sum formula computes n(n + 1) before halving it, which can overflow a 32-bit integer for large enough n.
O(n)O(1)1class Solution {
2 public int missingNumber(int[] nums) {
3 int n = nums.length;
4 int expectedSum = n * (n + 1) / 2;
5 int actualSum = 0;
6 for (int num : nums) {
7 actualSum += num;
8 }
9 return expectedSum - actualSum;
10 }
11}Optimal — XOR Everything
OptimalXOR together every number from 0 to n with every value actually in the array. Every number that appears in both the full range and the array cancels itself out, since XOR-ing a value with itself gives 0 — the only number left standing is the one that's in the full range but missing from the array. Unlike the sum formula, XOR-ing integers can never overflow.
O(n)O(1)1class Solution {
2 public int missingNumber(int[] nums) {
3 int n = nums.length;
4 int result = n;
5 for (int i = 0; i < n; i++) {
6 result ^= i ^ nums[i];
7 }
8 return result;
9 }
10}