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.
This approach uses the formula for the sum of the first n natural numbers: Sum = n * (n + 1) / 2. By calculating the sum of the numbers from the array and subtracting it from the expected sum, we can find the missing number.
The above C program calculates the sum of the array elements and subtracts it from the sum of numbers in the range [0, n], which is calculated using the formula n * (n + 1) / 2. This gives the missing number.
Time Complexity: O(n), where n is the length of the array.
Space Complexity: O(1), as no additional space is used beyond variables.
An efficient approach is using XOR. XORing a number with itself results in zero (n ^ n = 0), and XOR of any number with zero keeps the number unchanged (n ^ 0 = n). By XORing all indices and array elements together, each number present in both will cancel out, leaving the missing number.
This C solution utilizes XOR properties: iterates through the array, XORing indices and elements to find the single non-repeated element, which is the missing number.
Time Complexity: O(n), iterating through the array.
Space Complexity: O(1), using constant space.
The XOR operation has the following properties:
x \oplus 0 = x;x \oplus x = 0;Therefore, we can traverse the array, perform XOR operation between each element and the numbers [0,..n], and the final result will be the missing number.
The time complexity is O(n), where n is the length of the array. The space complexity is O(1).
Python
Java
C++
Go
TypeScript
Rust
JavaScript
PHP
We can also solve this problem using mathematics. By calculating the sum of [0,..n], subtracting the sum of all numbers in the array, we can obtain the missing number.
The time complexity is O(n), where n is the length of the array. The space complexity is O(1).
Python
Java
C++
Go
TypeScript
Rust
JavaScript
| Approach | Complexity |
|---|---|
| Sum Formula Approach | Time Complexity: O(n), where n is the length of the array. |
| Bit Manipulation using XOR | Time Complexity: O(n), iterating through the array. |
| Bitwise Operation | — |
| Mathematics | — |
| 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. |
Missing Number - Blind 75 - Leetcode 268 - Python • NeetCode • 170,480 views views
Watch 9 more video solutions →Practice Missing Number with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor