Watch 10 video solutions for Missing Number, a easy level problem involving Array, Hash Table, Math. This walkthrough by NeetCode has 139,224 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 are given 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 in linear time without using extra memory.
Approach 1: Sum Formula (O(n) time, O(1) space)
The range 0..n has a known mathematical sum: n * (n + 1) / 2. Compute this expected total, then iterate through the array and subtract every element from it. The remainder is the missing number. This works because the array contains every value except one, so the difference between the theoretical sum and the actual array sum reveals the missing element. The algorithm performs a single pass through the array and uses constant extra memory. This approach relies on basic arithmetic properties and is commonly discussed when practicing math-based problem solving on arrays.
Approach 2: Bit Manipulation using XOR (O(n) time, O(1) space)
The XOR operation has two useful properties: a ^ a = 0 and a ^ 0 = a. If you XOR all numbers from 0..n and also XOR all elements of the array, every number that appears twice cancels itself out. The only value left after all cancellations is the missing number. Implementation is straightforward: iterate once through the array while XOR-ing the index and element values. This avoids potential overflow from arithmetic sums and demonstrates practical use of bit manipulation. The space usage remains constant because only a single accumulator variable is required.
Recommended for interviews: Both approaches run in O(n) time with O(1) extra space and are considered optimal. Interviewers often expect the sum formula first because it shows quick recognition of the mathematical pattern in an array problem. The XOR solution demonstrates deeper understanding of bitwise operations and edge-case safety (such as avoiding integer overflow). Showing the sum formula initially and then mentioning the XOR variant signals strong problem-solving breadth.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sum Formula | O(n) | O(1) | General case when integer overflow is not a concern and you want the simplest mathematical solution |
| Bit Manipulation (XOR) | O(n) | O(1) | When avoiding overflow or demonstrating bit manipulation skills in interviews |