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?
The Missing Number problem asks you to identify the one number missing from an array containing n distinct numbers taken from the range 0 to n. A common and efficient strategy uses the mathematical sum formula. The expected sum of numbers from 0 to n can be calculated using n * (n + 1) / 2. By subtracting the actual sum of elements in the array from this expected value, the missing number can be determined in a single pass.
Another elegant method uses bit manipulation with XOR. XORing all indices and array elements cancels out matching values, leaving only the missing number. This approach avoids overflow and also runs efficiently.
Alternative strategies include using a hash set to track seen numbers or sorting the array and checking for mismatches. However, the mathematical and XOR approaches are typically preferred in interviews because they achieve O(n) time with O(1) extra space.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Mathematical Sum Formula | O(n) | O(1) |
| XOR Bit Manipulation | O(n) | O(1) |
| Hash Set | O(n) | O(n) |
| Sorting | O(n log n) | O(1) or O(n) |
NeetCode
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.
Time Complexity: O(n), where n is the length of the array.
Space Complexity: O(1), as no additional space is used beyond variables.
1#include <stdio.h>
2
3int missingNumber(int* nums, int numsSize) {
4 int total = numsSize * (numsSize + 1) / 2;
5 int sum = 0;
6 for (int i = 0; i < numsSize; i++) {
7 sum += nums[i];
8 }
9 return total - sum;
10}
11
12int main() {
13 int nums[] = {3, 0, 1};
14 int missing = missingNumber(nums, 3);
15 printf("Missing number: %d\n", missing);
16 return 0;
17}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.
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.
Time Complexity: O(n), iterating through the array.
Space Complexity: O(1), using constant space.
1using System;
public class Solution {
public int MissingNumber(int[] nums) {
int xorResult = 0;
for (int i = 0; i < nums.Length; i++) {
xorResult ^= i ^ nums[i];
}
xorResult ^= nums.Length;
return xorResult;
}
public static void Main(string[] args) {
int[] nums = {3, 0, 1};
Solution sol = new Solution();
Console.WriteLine("Missing number: " + sol.MissingNumber(nums));
}
}Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
The most optimal approaches are the mathematical sum formula and the XOR method. Both scan the array once and compute the missing value in O(n) time with O(1) extra space, making them ideal for coding interviews.
The XOR approach works because XOR cancels out identical numbers. When you XOR all indices and all array values together, every paired number disappears, leaving only the missing value as the final result.
A hash set can be used to store all elements and check which number from 0 to n is missing. While simple to implement, it requires O(n) extra space, so interviewers often prefer the math or XOR approach instead.
Yes, Missing Number is a common introductory array problem asked in technical interviews, including FAANG companies. It tests understanding of arrays, mathematical reasoning, and bit manipulation techniques.
This C# program leverages XOR properties to find the missing element by processing indices and numbers simultaneously.