Problem
Given an array containing n distinct numbers in the range [0, n], return the one number that is missing.
Example
Input: [3,0,1]
Output: 2Input: [9,6,4,2,3,5,7,0,1]
Output: 8Solution
Sum formula: expected sum = n*(n+1)/2. Subtract actual sum to get the missing number.
def missing_number(nums):
n = len(nums)
return n * (n + 1) // 2 - sum(nums)function missingNumber(nums) {
const n = nums.length;
const expected = (n * (n + 1)) / 2;
const actual = nums.reduce((a, b) => a + b, 0);
return expected - actual;
}int missingNumber(vector<int>& nums) {
int n = nums.size();
int expected = n * (n + 1) / 2;
int actual = 0;
for (int x : nums) actual += x;
return expected - actual;
}public int missingNumber(int[] nums) {
int n = nums.length;
int expected = n * (n + 1) / 2;
int actual = 0;
for (int x : nums) actual += x;
return expected - actual;
}Complexity
- Time: O(n)
- Space: O(1)
Explanation
The Gauss sum formula gives us the expected sum without iterating. Subtracting the actual sum reveals the missing number. Alternative approach: XOR all numbers from 0 to n with all numbers in the array.
Comments
Join the discussion. Got a question, found an issue, or want to share your experience?