268. Missing Number - Detailed Explanation
Problem Statement
Description:
You are given an array nums containing n distinct numbers taken from the range [0, n]. In other words, there are n + 1 possible numbers, but the array contains only n of them. Your task is to find and return the only number in the range that is missing from the array.
Constraints:
-
The array
numscontains n distinct integers. -
The integers are in the range [0, n].
-
You must solve the problem without using extra space for another array (if possible) and with linear time complexity.
Example 1:
- Input:
nums = [3, 0, 1] - Output:
2 - Explanation:
The numbers in the range [0, 3] are[0, 1, 2, 3]. Since2is missing from the array, the output is2.
Example 2:
- Input:
nums = [0, 1] - Output:
2 - Explanation:
The range is[0, 1, 2]and the missing number is2.
Example 3:
- Input:
nums = [9,6,4,2,3,5,7,0,1] - Output:
8 - Explanation:
The numbers in the range [0, 9] are[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]. The number8is missing.
Hints Before the Solution
-
Hint 1: Consider the total sum of numbers from 0 to n. Compare it with the sum of the given array. The difference will be the missing number.
-
Hint 2: Alternatively, think about using bitwise XOR. If you XOR all indices and array values together, the duplicate XOR operations will cancel out, leaving the missing number.
-
Hint 3: A brute-force approach could involve sorting the array and scanning through the numbers, but there are more efficient solutions.
Approaches
Approach 1: Summation Formula
Explanation:
- Idea:
The sum of the first n natural numbers (including 0) is given by the formula:
[ \text{expected\_sum} = \frac{n \times (n+1)}{2} ] Compute the sum of elements in the given array and subtract it from the expected sum. The result is the missing number. - Steps:
- Calculate
expected_sumfor numbers from 0 to n. - Compute
actual_sumby summing all elements innums. - The missing number is
expected_sum - actual_sum.
- Calculate
- Complexity:
- Time: O(n)
- Space: O(1)
Approach 2: Bitwise XOR
Explanation:
- Idea:
XOR has a unique property where a number XORed with itself is 0, and a number XORed with 0 is the number itself. By XORing all indices and all numbers innums, every number that appears twice will cancel out, leaving the missing number. - Steps:
-
Initialize a variable
xorwith 0. -
XOR all numbers from 0 to n with
xor. -
XOR every element in
numswith the same variable. -
The final value of
xoris the missing number.
-
- Complexity:
- Time: O(n)
- Space: O(1)
Approach 3: Sorting (Less Optimal)
Explanation:
-
Idea:
Sort the array and then iterate through it, comparing each number with its index. The first index that does not match the number is the missing number. -
Steps:
- Sort the array.
- Loop through the array and if
nums[i]does not equali, theniis the missing number. - If all indices match, then the missing number is n.
-
Complexity:
- Time: O(n log n) due to sorting
- Space: O(1) or O(n) depending on the sorting algorithm used.
Python Code
Below is the Python implementation using the Summation Formula approach:
Below is the Python code using the XOR method:
Java Code
Below is the Java implementation using the Summation Formula approach.
Java Code
Below is the java code using the XOR approach:
Complexity Analysis
-
Time Complexity:
- Both the summation method and the XOR method require a single pass (or two simple passes) through the array, giving a time complexity of O(n).
-
Space Complexity:
- Both approaches use O(1) extra space.
Step-by-Step Walkthrough & Visual Example
Consider the input nums = [3, 0, 1]:
-
Determine n:
The length of the array is 3, so the full range is [0, 3] (i.e., possible numbers are 0, 1, 2, 3). -
Using the Summation Formula:
- Calculate expected sum:
[ \text{expected\_sum} = \frac{3 \times (3+1)}{2} = \frac{12}{2} = 6 ] - Calculate actual sum:
[ \text{actual\_sum} = 3 + 0 + 1 = 4 ] - The missing number is:
[ 6 - 4 = 2 ]
- Calculate expected sum:
-
Using the XOR Method:
- XOR numbers from 0 to 3:
[ 0 \oplus 1 \oplus 2 \oplus 3 = X ] - XOR the result with all numbers in
nums(3, 0, 1):
The numbers that appear in both groups cancel out, leaving 2 as the final result.
- XOR numbers from 0 to 3:
Common Mistakes, Edge Cases & Alternative Variations
Common Mistakes:
- Incorrect Formula:
Mistakenly using the formula for the sum of the first n numbers when the range is [0, n]. - Overflow Concerns:
In some languages, summing large numbers might cause overflow. However, given the constraints, this is typically not an issue. - Not Handling an Empty Array:
Although the problem guarantees at least one number, always consider how your solution would behave ifnumswere empty.
Edge Cases:
-
Single Element Array:
Ifnumscontains only one element (either 0 or 1), ensure the solution correctly returns the missing number. -
Array in Sorted Order vs. Unsorted Order:
The solution should work regardless of the order of elements in the input array.
Alternative Variations:
-
Finding Multiple Missing Numbers:
A variant of the problem may involve finding all missing numbers in an array that should contain a range. -
Using Extra Space:
An approach using a boolean array or hash set to mark seen numbers can also be used, but it requires extra space.
Related Problems for Further Practice
GET YOUR FREE
Coding Questions Catalog
