Missing Number

How you get there

1. 1The full range 0..n sums to n(n+1)/2.
2. 2Subtracting the actual sum leaves the missing value.
3. 3XOR-ing indices with values also cancels everything present.

Solution

def missing_number(nums: list[int]) -> int:
    n = len(nums)
    return n * (n + 1) // 2 - sum(nums)

Time

O(n)

Space

O(1)

What goes wrong

In languages with fixed-width integers the sum can overflow; XOR avoids that, though Python cannot overflow.