find missing number in array

Given an array [0...n] with a missing number, write a program to efficiently find the missing number.

The solution is truly beautiful, and consists of:

• a/ xoring all the numbers in the given range with the missing number
• b/ xoring all the numbers in the range [0...n]
• a xor b

functional style

1from functools import reduce
2from operator import ixor
3
4find_missing = lambda A: ixor(reduce(ixor, arr), reduce(ixor, range(len(A) + 1)))
5find_missing([0, 1, 2, 3, 4, 5, 6, 7, 8, 10])

Result:

19