The Missing Value
Problem
A list holds n distinct values drawn from 0 up to n, in any order, so exactly one value of that range is absent. Find it in one pass using constant extra space, which rules out sorting and rules out a set of everything seen.
Examples
Input: nums = [3, 0, 1]
Output: 2Input: nums = [9, 6, 4, 2, 3, 5, 7, 0, 1]
Output: 8Input: nums = [0]
Output: 1
Why: edge case, the missing value can be n itselfHints
0 / 3
Every position in the list has an index, and those indexes cover almost the same range as the values themselves.
Pair each index with the value sitting at it. Only one member of the full range ends up without a partner, and you need an operation where a matched pair disappears.
XOR every index and every value together, and throw n into the mix as the one index that does not exist. Each present value cancels against its matching number, and the survivor is the value that was never there.
Solution
The indexes 0 through n-1 plus the extra value n cover the same range as the complete list would, so folding indexes and values together with XOR pairs almost everything off. A value cancels against the equal number contributed by the index side, leaving only the number nobody supplied. Starting the accumulator at n is what supplies the one index the list does not have. Time is O(n) in a single pass, and space is O(1).
def missing(nums):
answer = len(nums) # n, the index the list does not have
for i, v in enumerate(nums):
answer ^= i ^ v # each matched pair cancels itself out
return answer
print(missing([3, 0, 1])) # -> 2
print(missing([9, 6, 4, 2, 3, 5, 7, 0, 1])) # -> 8
print(missing([0])) # -> 1
print(missing([1])) # -> 0Stuck on the idea rather than the code? XOR Tricks covers it.