Find The One
Is it possible to design an algorithm that uses constant space for the following function?
Input: \(2n + 1\) non-negative integers; every integer appears twice, except one that appears only once.
Output: The integer that appears exactly once.
Details and Assumptions: Assume that storing each integer takes constant amount of space regardless of the number of bits in the integer.