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?

Difficulty: introductory

Starter code:

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        

Solutions:
class Solution:
     def missingNumber(self, nums):
         """
         :type nums: List[int]
         :rtype: int
         """
         if 0 not in nums:
             return 0
         array=sorted(nums)
         for i in range(len(array)):
             try:
                 dif=array[i+1]-array[i]
                 if dif!=1:
                     return array[i]+1
             except:
                 return array[-1]+1


class Solution:
     def missingNumber(self, nums):
         """
         :type nums: List[int]
         :rtype: int
         """
         nums.append(nums[0])
         for i in range(len(nums)):
           v = nums[i]
           while v != nums[v]:
             nums[v], v = v, nums[v]
         for i, num in enumerate(nums):
           if i != num:
             return i
         return None

class Solution:
     def missingNumber(self, nums):
         """
         :type nums: List[int]
         :rtype: int
         """
         n = len(nums)
         s = n*(n+1)//2
         return s - sum(nums)


class Solution:
     def missingNumber(self, nums):
         expected_sum = len(nums)*(len(nums)+1)//2
         actual_sum = sum(nums)
         return expected_sum - actual_sum

class Solution:
     def missingNumber(self, nums):
         res = len(nums)
         for i in range(len(nums)):
             res = res ^ i
             res = res ^ nums[i]
         return res


class Solution:
     def missingNumber(self, nums):
         """
         :type nums: List[int]
         :rtype: int
         """
         res = len(nums)
         # 异或表示相同数为0，索引和数组的数应该两两相对
         for i,x in enumerate(nums):
             res ^=i
             res ^=x
         return res

class Solution:
     def missingNumber(self, nums):
         """
         :type nums: List[int]
         :rtype: int
         """
         n = len(nums)
         return int((1+n)*n/2-sum(nums))

class Solution:
     def missingNumber(self, nums):
         
         return (sum(range(len(nums)+1)) - sum(nums))
         """ 
         :type nums: List[int]
         :rtype: int
         """

class Solution:
     def missingNumber(self, nums):
         """
         :type nums: List[int]
         :rtype: int
         """
         
         length = len(nums)+1
         total = sum(i for i in range(length))
         
         nums_total = sum(nums)
         
         return total-nums_total
         
         


class Solution:
     def missingNumber(self, array):
         """ Time complexity: O(n). Space complexity: O(1).
         """
         n = len(array)
         for i, num in enumerate(array):
             n = n ^ i ^ num
         return n

class Solution:
     def missingNumber(self, nums):
         """
         :type nums: List[int]
         :rtype: int
         """
         s = set()
         for num in nums:
             s.add(num)
         for i in range(len(nums) + 1):
             if i in s:
                 continue
             else:
                 return i

class Solution:
     def missingNumber(self, nums):
         """
         :type nums: List[int]
         :rtype: int
         """
         import functools
         res1 = functools.reduce(lambda x,y:x^y, [i for i in range(len(nums)+1)])
         res2 = functools.reduce(lambda x,y:x^y, nums )
         return res1^res2


class Solution:
     def missingNumber(self, nums):
         """
         :type nums: List[int]
         :rtype: int
         """
         total = 0
         for num in range(len(nums)+1):
             total += num
         return total - sum(nums)

class Solution:
     def missingNumber(self, nums):
         """
         :type nums: List[int]
         :rtype: int
         """
         x = [0]*(len(nums)+1)
         for e in nums:
             x[e] = 1
         return x.index(0)

class Solution:
     def missingNumber(self, nums):
         """
         :type nums: List[int]
         :rtype: int
         """
         srted = sorted(nums)
 
         for i in range(0,len(srted)):
             if srted[i] != i:
                 return i
         
         return i+1