Jane Street Interview Question
Given an array of paired integers, write an algorithm to find the integer that is not paired, using constant space.
Interview Answer
Anonymous
Feb 24, 2016
XOR them all together. I can't believe this counts as an interview question. In Haskell it is literally one line: findUnpaired = foldr1 Data.Bits.xor This works since: xor is associative and commutative, xor has identity 0, xor of two equal numbers gives 0.
2