Missing Number
Problem link: https://leetcode.com/problems/missing-number/
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.
Input
An array of n distinct integers in the range [0, n].
Output
The single missing integer.
Example
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.
Explanation
The array has a length of 3, meaning the numbers should be 0, 1, 2, 3. Comparing the sum of the expected range to the actual sum reveals the missing value.
Brute Force
Intuition
Sort the array first. After sorting, the number at each index should match the index itself (nums[i] == i). The first index where this fails is the missing number.
Approach
- Sort the input array nums.
- Iterate through the array from i = 0 to n-1.
- If nums[i] != i, return i.
- If the loop completes, the missing number is n.
Dry Run
nums = [3,0,1] Sorted: [0,1,3] i=0: 0 == 0 (OK) i=1: 1 == 1 (OK) i=2: 3 != 2 (Found! Return 2)
Code (Java)
Complexity Analysis
Sorting the array takes O(N log N) time.
Optimal Solution
Intuition
Mathematical Approach: Use the formula for the sum of the first n natural numbers. Subtract the actual sum of the array from this expected sum to find the missing number.
Approach
- Calculate n (length of nums).
- Calculate expectedSum = n * (n + 1) / 2.
- Calculate actualSum by adding all elements in nums.
- Return expectedSum - actualSum.
Dry Run
nums = [3,0,1], n = 3 Expected: 3 * (4) / 2 = 6 Actual: 3 + 0 + 1 = 4 Missing: 6 - 4 = 2
Code (Java)
class Solution {
public int missingNumber(int[] nums) {
int n = nums.length;
int expectedSum = n * (n + 1) / 2;
int actualSum = 0;
for (int num : nums) {
actualSum += num;
}
return expectedSum - actualSum;
}
}
Complexity Analysis
We iterate through the array once to calculate the actual sum.
Quick Revision (Brute Force)
- Sort and compare with index
- O(N log N) time
Quick Revision (Optimal)
- Math: Expected Sum - Actual Sum
- XOR: XOR all indices and values
- O(N) time, O(1) space