Missing Number
Given an array of integers from 1 to n, find the missing number in the array.
Constraints:
- 1 <= n <= 10^4
- The array contains all integers from 1 to n except one.
Examples:
Input: [1, 2, 3, 5]
Output: 4
Explanation: The missing number in the array is 4.
Solutions
Mathematical Approach
Time: O(n)Space: O(1)
The mathematical approach calculates the sum of all numbers from 1 to n using the formula n * (n + 1) / 2, then subtracts the sum of the numbers in the array to find the missing number.
function findMissingNumber(nums) {
let n = nums.length + 1;
let sum = Math.floor((n * (n + 1)) / 2);
return sum - nums.reduce((a, b) => a + b, 0);
}
Follow-up:
What if the array contains duplicates?
