Find three numbers appeared only once
- by shilk
In a sequence of length n, where n=2k+3, that is there are k unique numbers appeared twice
and three numbers appeared only once.
The question is: how to find the three unique numbers that appeared only once?
for example, in sequence 1 1 2 6 3 6 5 7 7 the three unique numbers are 2 3 5.
Note:
3<=n<1e6 and the number will range from 1 to 2e9
Memory limits: 1000KB , this implies that we can't store the whole sequence.
Method I have tried(Memory limit exceed):
I initialize a tree, and when read in one number I try to remove it from the tree, if the
remove returns false(not found), I add it to the tree. Finally, the tree has the three numbers. It works, but is Memory limit exceed.
I know how to find one or two such number(s) using bit manipulation. So I wonder if
we can find three using the same method(or some method similar)?
Method to find one/two number(s) appeared only once:
If there is one number appeared only once, we can apply XOR to the sequence to find it.
If there are two, we can first apply XOR to the sequence, then separate the sequence into 2
parts by one bit of the result that is 1, and again apply XOR to the 2 parts, and we will find the answer.
