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?

Source: leetcode | Difficulty: EASY
Tags: Bit manipulation

Sorting

Data structures

Mathematics

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

Solutions:
class Solution:

	def missingNumber(self, nums):
		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):
		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):
		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):
		res = len(nums)
		for (i, x) in enumerate(nums):
			res ^= i
			res ^= x
		return res


class Solution:

	def missingNumber(self, nums):
		return sum(range(len(nums) + 1)) - sum(nums)


class Solution:

	def missingNumber(self, nums):
		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):
		n = len(array)
		for (i, num) in enumerate(array):
			n = n ^ i ^ num
		return n


class Solution:

	def missingNumber(self, nums):
		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):
		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):
		total = 0
		for num in range(len(nums) + 1):
			total += num
		return total - sum(nums)


class Solution:

	def missingNumber(self, nums):
		x = [0] * (len(nums) + 1)
		for e in nums:
			x[e] = 1
		return x.index(0)


class Solution:

	def missingNumber(self, nums):
		srted = sorted(nums)
		for i in range(0, len(srted)):
			if srted[i] != i:
				return i
		return i + 1