# Finding singletons

For $$i\in\{1,2,3\}$$, there are $$2n+i$$ integers consisting of $$n+i$$ unique ones. $$n$$ of them appear twice, and $$i$$ of them just once. Find these singletons in $$O(n)$$ time with $$O(1)$$ space.

Solution with $$O(\log n)$$ space:
Too bad, that finding median takes $$O(\log n)$$ space! Let $$algorithm_i$$ be the algorithm that tackles $$i$$ singletons. $$algorithm_1$$ is to just XOR all numbers.

$$algorithm_2$$: find median $$m$$; if it's a singleton, apply $$algorithm_1$$ to the rest; otherwise, count how many numbers are below and above $$m$$. If both are odd, apply $$algorithm_1$$ to each set separately, otherwise XOR all numbers in each set separately to find out which has two singletons, and then apply $$algorithm_2$$ to that recursively.

$$algorithm_3$$: find median $$m$$; if it's a singleton, apply $$algorithm_2$$ to the rest; otherwise, count how many numbers are below and above $$m$$ -- one set has even size and the other has odd size.XOR all numbers in the even-sized set to check if it contains singleton. If it does, apply $$algorithm_2$$ to it and apply $$algorithm_1$$ to the other; otherwise apply $$algorithm_3$$ recursively to the other.

Real solution:
$$algorithm_2$$: XOR all numbers to get $$s$$. From $$s$$ find a bit $$b$$ that is $$1$$ in $$s$$. Now there must be odd numbers with bit $$b$$ equal to $$0$$ and odd numbers with bit $$b$$ equal to $$1$$. XOR each set separately to get these two singletons.

$$algorithm_3$$: If $$s$$ is not zero, find a similar bit $$b$$. There are odd numbers with $$b$$ set to $$1$$ and even numbers with $$b$$ set to $$0$$. Figure out if the second set has singleton by XOR, and act accordingly. If $$s=0$$, find a bit $$b$$ that not all numbers agree. There are even numbers with $$b$$ set to $$1$$ and odd numbers with $$b$$ set to $$0$$. Decide if the first set has two singletons by XOR and then proceed.