While it seems unreasonable to expect the XOR solutions in interviews, it is quite fun to figure out how they work. As it turns out, they are all based on the same fundamental trick, which we will derive in a bottom-up way in this post. Afterwards we will look at a bunch of applications of that XOR trick ™, such as solving this popular interview question:

You are given an array of n - 1 integers which are in the range between 1 and n. All numbers appear exactly once, except one number, which is missing. Find this missing number.

Of course, there are a number of straightforward ways to solve this problem, but there is also a perhaps surprising one using XOR.

Created on Nov 8, 2020
By @gurlic