Watch 10 video solutions for Missing Number, a easy level problem involving Array, Hash Table, Math. This walkthrough by NeetCode has 170,480 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
Example 1:
Input: nums = [3,0,1] Output: 2 Explanation: n = 3 since there are 3 numbers, so all numbers are in the range [0,3]. 2 is the missing number in the range since it does not appear in nums.
Example 2:
Input: nums = [0,1] Output: 2 Explanation: n = 2 since there are 2 numbers, so all numbers are in the range [0,2]. 2 is the missing number in the range since it does not appear in nums.
Example 3:
Input: nums = [9,6,4,2,3,5,7,0,1] Output: 8 Explanation: n = 9 since there are 9 numbers, so all numbers are in the range [0,9]. 8 is the missing number in the range since it does not appear in nums.
Constraints:
n == nums.length1 <= n <= 1040 <= nums[i] <= nnums are unique.
Follow up: Could you implement a solution using only O(1) extra space complexity and O(n) runtime complexity?
Problem Overview: You get an array containing n distinct numbers taken from the range 0..n. Exactly one number from that range is missing. The task is to identify the missing value efficiently without modifying the array.
Approach 1: Sum Formula Approach (O(n) time, O(1) space)
This approach relies on a simple mathematical observation. The sum of numbers from 0 to n is n * (n + 1) / 2. If you iterate through the array and compute the actual sum of its elements, the difference between the expected sum and the actual sum gives the missing number. The algorithm performs one pass through the array and a constant amount of arithmetic work.
The key insight is that the array contains every value in the range except one. Subtracting the observed total from the theoretical total reveals exactly which value is absent. This approach uses constant extra memory and avoids sorting or additional data structures, which makes it ideal for large inputs. The technique is rooted in simple math properties applied to an array.
Approach 2: Bit Manipulation using XOR (O(n) time, O(1) space)
The XOR method leverages a useful property of the XOR operation: a ^ a = 0 and a ^ 0 = a. If you XOR all numbers from 0..n and also XOR every element in the array, every number that appears in both sets cancels out. The only value left after all XOR operations is the missing number.
Implementation is straightforward. Iterate through the array while maintaining a running XOR of indices and values. For example, XOR the index and the element during the same loop. At the end, XOR with n to complete the full range. Because XOR operations are constant time and you only traverse the array once, the algorithm runs in linear time with constant extra space.
This technique is common in problems involving unique or missing elements and highlights the power of bit manipulation. It avoids potential integer overflow issues that may appear with the arithmetic sum formula in languages with strict integer limits.
Recommended for interviews: Both approaches are considered optimal and run in O(n) time with O(1) space. Interviewers often expect either the sum formula or the XOR solution. The sum formula demonstrates mathematical reasoning and clean code, while the XOR approach shows deeper understanding of bit operations. Explaining both during an interview signals strong problem-solving range.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sum Formula | O(n) | O(1) | General case when arithmetic overflow is not a concern and you want the simplest implementation. |
| Bit Manipulation (XOR) | O(n) | O(1) | Preferred when demonstrating bit manipulation skills or avoiding overflow in languages with limited integer ranges. |