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.
def find_missing_number(nums):
n = len(nums) + 1; sum_n = n * (n + 1) // 2; return sum_n - sum(nums)Follow-up:
What if the array contains duplicates?
