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.
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.length1 <= n <= 1040 <= nums[i] <= nnums are unique.Source
def missing_number(nums):
"""Using a Hash Table.
Time complexity: O(n)
Space Complexity: O(n)
"""
my_set = set(nums)
for i in range(len(nums)+1):
if number not in my_set:
return number
def missing_number(nums):
"""Using sort
Time complexity: O(nlogn)
Space Complexity: O(1)
"""
nums.sort()
for i, n in enumerate(nums):
if n != i:
return i
return len(nums)
nums = [3,0,1]
missing_number(nums)
2
nums = [0,1]
missing_number(nums)
2
nums = [1]
missing_number(nums)
0
nums = [9,6,4,2,3,5,7,0,1]
missing_number(nums)
8
Could you implement a solution using only O(1) extra space complexity and O(n) runtime complexity?
def missing_number(nums):
"""Using XOR which is its own inverse (0^x = x and x^x = 0)
Time complexity: O(n)
Space Complexity: O(1)
"""
missing = len(nums)
for i, a in enumerate(nums):
missing = missing ^ i ^ a # in the end, we have twice 0 ^ 1 ^ 2 ^ ... ^ n ^ n+1 but for missing number
# i=0: n+1 ^ 0 ^ a(0)
# i=1: n+1 ^ 0 ^ a(0) ^ 1 ^ a(1)
# i=2: n+1 ^ 0 ^ a(0) ^ 1 ^ a(1) ^ 2 ^ a(2)
# ...
# i= n-1: n+1 ^ 0 ^ 1 ^ 2 ^ ... ^ n-1 ^ a(0) ^ a(1) ^ a(2) ^ ... ^ a(n-1)
# i= n: n+1 ^ 0 ^ 1 ^ 2 ^ ... ^ n-1 ^ n ^ a(0) ^ a(1) ^ a(2) ^ ... ^ a(n-1) ^ a(n)
return missing
def missing_number(nums):
"""Using Gauss formula: sum(0..n) = n(n+1)/2
Time complexity: O(n)
Space Complexity: O(1)
"""
expected_sum = len(nums)*(len(nums)+1)//2
actual_sum = sum(nums)
return expected_sum - actual_sum
nums = [3,0,1]
missing_number(nums)
2
nums = [0,1]
missing_number(nums)
2
nums = [1]
missing_number(nums)
0
nums = [9,6,4,2,3,5,7,0,1]
missing_number(nums)
8