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.
int findMissingNumber(vector<int>& nums) {
int n = nums.size() + 1;
int sum = n * (n + 1) / 2;
int sumNums = 0;
for (int num : nums) {
sumNums += num;
}
return sum - sumNums;
}Follow-up:
What if the array contains duplicates?
