Given an array containingndistinct numbers taken from0, 1, 2, ..., n
, find the one that is missing from the array.
For example,
Givennums=[0, 1, 3]
return2
.
Note:
Your algorithm should run in linear runtime complexity. Could you implement it using only constant extra space complexity?
URL: https://leetcode.com/problems/missing-number/
class Solution(object):
def missingNumber(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
if not nums:
return None
else:
xor_prod = 0
xor_prod_index = 0
for i in range(len(nums)+1):
xor_prod_index ^= i
for i in range(len(nums)):
xor_prod ^= nums[i]
return xor_prod ^ xor_prod_index