Missing Number
Understanding the Problem
We have an array of n distinct integers, and these integers come from the range [0, n]. The range has n + 1 numbers but the array holds only n of them, so exactly one number is missing. Our job is to find it.
We know the complete set in advance. If n = 3, the full set is {0, 1, 2, 3}. The array gives us 3 of those 4 numbers, and we need to find the one left out. Because the range is fixed and known, we can compare the array against it directly instead of searching for an arbitrary value, and that opens up arithmetic and bitwise techniques.
Key Constraints:
n == nums.lengthwith1 <= n <= 10^4. The expected sumn * (n + 1) / 2reaches about 5 * 10^7 at the maximum n, well within a 32-bit signed integer, so a sum-based approach is safe from overflow here.0 <= nums[i] <= n. Every value lies in the range [0, n], so an auxiliary boolean array of size n + 1 is also an option.- All numbers are unique. Each number from [0, n] appears either zero or one times, so there are no duplicates to handle.
Approach 1: Hash Set
Intuition
Put every array element into a hash set, then scan the expected range [0, n] and return the first number that the set does not contain. Membership checks against a hash set are O(1) on average, so the whole scan is linear.
Algorithm
- Create a hash set containing all elements of
nums. - Loop through every integer from 0 to n (where n is the length of
nums). - For each integer, check if it exists in the set.
- Return the first integer not found in the set.
Example Walkthrough
Code
- Time Complexity: O(n). Building the hash set takes O(n). Checking membership for each of the n+1 numbers takes O(1) per lookup on average. Total: O(n).
- Space Complexity: O(n). The hash set stores all n elements from the array.
The hash set uses O(n) extra space to store every element. The next approach drops that to O(1) by using the arithmetic structure of the range [0, n] instead of a separate data structure.
Approach 2: Gauss' Formula (Sum)
Intuition
We know the sum of every number in [0, n] without looking at the array. The formula n * (n + 1) / 2 gives the sum of the integers from 0 to n. Compute the actual sum of the array and subtract it from this expected sum, and the difference is the missing number.
The reason is that removing one number from a complete set reduces the total by exactly that number's value. So expectedSum - actualSum recovers the value that was removed.
If every number in [0, n] were present, the array would sum to exactly n * (n + 1) / 2. Exactly one number M is absent, so the actual sum is n * (n + 1) / 2 - M. Subtracting the actual sum from the expected sum gives M. Because all values are unique and bounded by n, no other value can account for the difference.
Algorithm
- Compute the expected sum:
n * (n + 1) / 2where n is the length of the array. - Compute the actual sum of all elements in
nums. - Return
expectedSum - actualSum.
Example Walkthrough
Code
- Time Complexity: O(n). One pass through the array to compute the sum.
- Space Complexity: O(1). Only uses a couple of integer variables.
The sum approach is O(n) time and O(1) space, which meets the follow-up requirement. For this problem's bounds the sum cannot overflow a 32-bit integer, but at larger bounds it could, and the next approach avoids addition entirely by computing the answer with XOR.
Approach 3: XOR (Bit Manipulation)
Intuition
XOR satisfies a ^ a = 0 and a ^ 0 = a: XOR-ing a number with itself cancels it, and XOR-ing with zero leaves it unchanged. XOR is also commutative and associative, so the order of operations does not matter.
XOR every index from 0 to n together with every value in the array. Each number that appears in both the index range and the array is XOR-ed twice and cancels to zero. The missing number appears only in the range, so it is XOR-ed once and remains as the final result.
Let M be the missing number. The computation is (0 ^ 1 ^ 2 ^ ... ^ n) ^ (nums[0] ^ nums[1] ^ ... ^ nums[n-1]). Every value except M appears exactly twice, once from the range and once from the array, contributing x ^ x = 0. M appears only once, from the range, so the result is 0 ^ M = M.
Algorithm
- Initialize
xorto 0. - XOR
xorwith each index from 0 to n. - XOR
xorwith each element ofnums. - After all operations,
xorholds the missing number. Return it.
Example Walkthrough
Code
- Time Complexity: O(n). Single pass through the array, doing constant work per element.
- Space Complexity: O(1). Only uses a single integer variable.