Leetcode: 268. Missing Number

Problem Statement

Pattern

Solution

Given an integer array \(a\) with \(n\) distinct numbers between \(0\) and \(n\), the task is to find the number from \(0\) to \(n\) missing in \(a\). To solve this problem, we can use two properties of XOR: \(a \oplus a = 0\) and \(a \oplus 0 = a\) for any integer \(a\). We compute \(X = 0 \oplus 1 \oplus 2 \oplus ... \oplus n\) and \(Y = a[0] \oplus a[1] \oplus ... \oplus a[n-1]\). As there is only one number missing from \(0\) to \(n\) in \(a\), we know that \(X \oplus Y\) will cancel out the duplicates and leave the only missing number. The solution has time complexity \(O(n)\) and space complexity \(O(1)\). 

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        ans = 0
        for n in nums:
            ans = ans ^ n
        for i in range(len(nums) + 1):
            ans = ans ^ i
        return ans

Cited by 1