Missing Number

Given an array nums containing n distinct numbers in the range [0, n], return the only number in the range that is missing from the array.

Follow up: Could you implement a solution using only O(1) extra space complexity and O(n) runtime complexity?

Examples: 

Example 1:

Input: nums = [3,0,1]
Output: 2
Explanation: n = 3 since there are 3 numbers, so all numbers are in the range [0,3]. 2 is the missing number in the range since it does not appear in nums.

Example 2:

Input: nums = [0,1]
Output: 2
Explanation: n = 2 since there are 2 numbers, so all numbers are in the range [0,2]. 2 is the missing number in the range since it does not appear in nums.

Example 3:

Input: nums = [9,6,4,2,3,5,7,0,1]
Output: 8
Explanation: n = 9 since there are 9 numbers, so all numbers are in the range [0,9]. 8 is the missing number in the range since it does not appear in nums.

Example 4:

Input: nums = [0]
Output: 1
Explanation: n = 1 since there is 1 number, so all numbers are in the range [0,1]. 1 is the missing number in the range since it does not appear in nums.

 Constraints:

• n == nums.length
• 1 <= n <= 104
• 0 <= nums[i] <= n
• All the numbers of nums are unique.

Algorithm:

1. Since n = nums.length and all the numbers of nums list are unique, we can find the one missing value in nums by computing the actual sum of the given nums list (using sum(nums) in Python) and subtracting it from the expected sum of adding all numbers upto n using natural number sum formula ( using (n * (n+1)//2) in Python).
2. The difference would yield the missing element, within the 0 to n range of unique numbers in the given nums list that we are looking for.

Test:

1.Test empty and None nums list.

2. Test with the missing element to be the value 0.

3. Test with the missing element to be the value n.

Solution:

Complexity:

Since sums(nums) would need to look at each element in the list to compute sum, and the natural number sum formula does not incur any additional time, the worst case time complexity is T = O(n). Since we are not using any auxiliary space, space complexity is, S = O(1).