Missing Number

Problem: Array contains $n$ distinct numbers from $0$ to $n$. One is missing. Find it.

XOR approach: XOR all array elements with $0, 1, 2, ..., n$. Pairs cancel, leaving the missing number.

function missingNumber(nums):
    n = nums.length
    result = n
    for i from 0 to n-1:
        result = result ^ i ^ nums[i]
    return result

Example: $[3, 0, 1]$, $n = 3$.

• XOR: $3 \oplus 0 \oplus 1 \oplus 0 \oplus 1 \oplus 2 \oplus 3 = 2$.
• Missing: $2$.

Alternative: Sum formula. Expected sum = $n(n+1)/2$. Subtract actual sum.

Both are $O(n)$ time, $O(1)$ space (excluding input). XOR avoids potential overflow.