[LeetCode] 268. Missing Number

Problem : https://leetcode.com/problems/missing-number/

Hash table based solution:

Time complexity = O ( N )

Space complexity = O ( N )

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        memo = set(nums)
        
        for n in nums:
            if n < len(nums) and n + 1 not in memo:
                return n + 1
        
        return 0

Bit manipulation based solution:

Time complexity = O ( N )

Space complexity = O ( 1 )

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

As it mentioned, the numbers are from 0 to n.

Now we use all of the valid indices [0, n] to XOR with all numbers. The result is the missing number.