Find Missing Number in Sequence
Given an array numbers of size n storing n different integers which fall within the range [0, n], implement a function to identify the missing element in the array. All numbers except one are present in the array. Find the missing number.
Input
numbers: number[]: An array of integers
Examples
Input: numbers = [1,3,0]
Output: 2
Explanation: The array has a size of 3, and within the range from 0 to 3, the number 2 is missing from the array
Input: numbers = [1]
Output: 0
Explanation: The array has a size of 1, and within the range from 0 to 1, the number 0 is missing from the array
Input: numbers = [3,0,4,2,1]
Output: 5
Explanation: The array has a size of 5, and within the range from 0 to 5, the number 5 is missing from the array
Constraints
- 1 <=
n<= 10,000 - 0 <=
numbers[i]<= n
Solution
TypeScript
Click to expand
export default function findMissingNumber(numbers: number[]): number{
const n = numbers.length;
const expectedSum = (n * (n + 1)) / 2;
const realSum = numbers.reduce((acc, val) => acc + val, 0);
return expectedSum - realSum;
}
Big O Analysis
- Time Complexity: O(n) - We iterate through the array once to calculate the sum.
- Space Complexity: O(1) - We use a constant amount of extra space.
Java
Click to expand
class Solution {
public int findMissingNumber(int[] numbers) {
int n = numbers.length;
int expectedSum = (n * (n + 1)) / 2;
int realSum = 0;
for(int num : numbers){
realSum += num;
}
return expectedSum - realSum;
}
}
Big O Analysis
- Time Complexity: O(n) - We iterate through the array once to calculate the sum.
- Space Complexity: O(1) - We use a constant amount of extra space.