Description
Given an array containing n distinct numbers taken from 0, 1, 2, ..., n, find the one that is missing from the array.
Example 1:
Input: [3,0,1]
Output: 2
Example 2:
Input: [9,6,4,2,3,5,7,0,1]
Output: 8
Note: Your algorithm should run in linear runtime complexity. Could you implement it using only constant extra space complexity?
Solutions
1. Sum
# Time: O(n)
# Space: O(1)
class Solution:
def missingNumber(self, nums: List[int]) -> int:
sum_nums = sum(nums)
sum_full = 0
for i in range(len(nums)+1):
sum_full += i
return sum_full - sum_nums
# 122/122 cases passed (140 ms)
# Your runtime beats 70.74 % of python3 submissions
# Your memory usage beats 83.87 % of python3 submissions (14 MB)
2. Bit Manipulation
# Time: O(n)
# Space: O(1)
class Solution:
def missingNumber(self, nums: List[int]) -> int:
n = len(nums)
xor = 0
for i in range(n):
xor = xor ^ i ^ nums[i]
return xor ^ n
# 122/122 cases passed (136 ms)
# Your runtime beats 85.31 % of python3 submissions
# Your memory usage beats 90.32 % of python3 submissions (14 MB)