Missing Number

Use the range invariant

For an array of length n containing distinct values from 0..n with one absent value, every expected number should cancel exactly one observed number. XOR is especially robust: initialize missing = n, then for each index i XOR both i and nums[i]. Equal operands cancel and 0 is neutral, leaving only the absent value.

A hash set is a clear O(n) time, O(n) space baseline. The XOR solution remains O(n) time with O(1) auxiliary space and does not mutate the array or risk arithmetic-sum overflow. Explain that it relies on exactly one missing value and no duplicates. Test [0] (answer 1), [1] (answer 0), and a missing endpoint. If the range starts at one or duplicates are permitted, clarify the contract because the invariant changes.