Problem Statement:
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.
Examples:
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 <= 10 40 <= nums[i] <= nAll the numbers of nums are unique.
Approach 1 (Brute-force with sorting and comparison):
- Sort the array.
- Loop from index
1ton - 1 - If
nums[i] != nums[i-1] + 1, returnnums[i-1] + 1as the missing number. - If no such mismatch is found:
- If
nums[0] != 0, return0. - Else return
n.
Time Complexity:
Time Complexity = O(n log n) Due to sorting the array.
Space Complexity:
Space Complexity = O(1) Sorting is done in-place, and only a few variables are used.
Dry Run
Input: Input: nums = [4, 2, 1, 0, 5]
After Sorting: nums = [0, 1, 2, 4, 5]
Check:
i = 1 → 1 == 0 + 1
i = 2 → 2 == 1 + 1
i = 3 → 4 != 2 + 1 → return 3
Final return 3
Output: 3
Visualisation:
var missingNumber = function(nums) {
nums.sort((a, b) => a - b);
if (nums[0] !== 0) return 0;
for (let i = 1; i < nums.length; i++) {
if (nums[i] !== nums[i - 1] + 1) {
return nums[i - 1] + 1;
}
}
return nums.length;
};
class Solution:
def missingNumber(self, nums):
nums.sort()
if nums[0] != 0:
return 0
for i in range(1, len(nums)):
if nums[i] != nums[i - 1] + 1:
return nums[i - 1] + 1
return len(nums)
import java.util.Arrays;
class Solution {
public int missingNumber(int[] nums) {
Arrays.sort(nums);
if (nums[0] != 0) return 0;
for (int i = 1; i < nums.length; i++) {
if (nums[i] != nums[i - 1] + 1) {
return nums[i - 1] + 1;
}
}
return nums.length;
}
}
#include <algorithm>
class Solution {
public:
int missingNumber(vector& nums) {
sort(nums.begin(), nums.end());
if (nums[0] != 0) return 0;
for (int i = 1; i < nums.size(); i++) {
if (nums[i] != nums[i - 1] + 1) {
return nums[i - 1] + 1;
}
}
return nums.size();
}
};
#include <stdlib.h>
int compare(const void* a, const void* b) {
return (*(int*)a - *(int*)b);
}
int missingNumber(int* nums, int numsSize) {
qsort(nums, numsSize, sizeof(int), compare);
if (nums[0] != 0) return 0;
for (int i = 1; i < numsSize; i++) {
if (nums[i] != nums[i - 1] + 1) {
return nums[i - 1] + 1;
}
}
return numsSize;
}
public class Solution {
public int MissingNumber(int[] nums) {
Array.Sort(nums);
if (nums[0] != 0) return 0;
for (int i = 1; i < nums.Length; i++) {
if (nums[i] != nums[i - 1] + 1) {
return nums[i - 1] + 1;
}
}
return nums.Length;
}
} Approach 2 (Optimal using Sum Formula):
- The sum of numbers from
0 to nis given by the formula: total_sum = (n × (n + 1)) / 2- Steps are as follows:
- Calculate total_sum using the
formula above. - Calculate the sum of all elements in the
input array. - The missing number is
total_sum - sum_of_array.
- Calculate total_sum using the
Time Complexity:
Time Complexity = O(n) We traverse the array once to compute the sum.
Space Complexity:
Space Complexity = O(1) Only a few variables are used, no extra space proportional to input size.
Dry Run
Input: nums = [3, 0, 1]
Step 1: n = nums.length = 3
Step 2: total_sum = (n * (n + 1)) / 2 = (3 * 4) / 2 = 6
Step 3: sum_of_array = 0
num = 3 → sum_of_array = 3
num = 0 → sum_of_array = 3
num = 1 → sum_of_array = 4
Step 4: return total_sum - sum_of_array = 6 - 4 = 2
Output: 2
var missingNumber = function(nums) {
let n = nums.length;
let total_sum = (n * (n + 1)) / 2;
let sum_of_array = 0;
for (let num of nums) {
sum_of_array += num;
}
return total_sum - sum_of_array;
};
class Solution:
def missingNumber(self, nums):
n = len(nums)
total_sum = n * (n + 1) // 2
sum_of_array = sum(nums)
return total_sum - sum_of_array
class Solution {
public int missingNumber(int[] nums) {
int n = nums.length;
int total_sum = n * (n + 1) / 2;
int sum_of_array = 0;
for (int num : nums) {
sum_of_array += num;
}
return total_sum - sum_of_array;
}
}
class Solution {
public:
int missingNumber(vector& nums) {
int n = nums.size();
int total_sum = n * (n + 1) / 2;
int sum_of_array = 0;
for (int num : nums) {
sum_of_array += num;
}
return total_sum - sum_of_array;
}
};
int missingNumber(int* nums, int numsSize) {
int total_sum = numsSize * (numsSize + 1) / 2;
int sum_of_array = 0;
for (int i = 0; i < numsSize; i++) {
sum_of_array += nums[i];
}
return total_sum - sum_of_array;
}
using System;
public class Solution {
public int MissingNumber(int[] nums) {
int n = nums.Length;
int total_sum = (n * (n + 1)) / 2;
int sum_of_array = 0;
foreach (int num in nums) {
sum_of_array += num;
}
return total_sum - sum_of_array;
}
} 
