Find Only Missing Number Between 0 and N

An array contains all the integers from 0 to n, except for one number which is missing. 
Write code to find the missing integer. Can you do it in O(n) time?

Example 1:
Input: [3,0,1]
Output: 2

Example 2:
Input: [9,6,4,2,3,5,7,0,1]
Output: 8

XOR All Numbers Algorithm

If we XOR all numbers and also 0 to N, we will get zero (Same Number XOR twice is zero). So, if only one number is missing, The XOR value will be the missing one. The time complexity is O(N) and space complexity is O(1) constant.

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        x = len(nums)
        for i, j in enumerate(nums):
            x ^= i
            x ^= j
        return x

Math Algorithm to Find Missing Number by Sum

We know the sum from 1 to N, and if we subtract each numbers in the array, we know the missing number.

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        n = len(nums)
        s = n * (n + 1) // 2
        for i in nums:
            s -= i
        return s

The Time Complexity is O(N) and the space complexity is O(1) constant.

–EOF (The Ultimate Computing & Technology Blog) —