I will get straight to the puzzle.
You have an array of $2n+3$ positive integers, such that each element appears exactly twice in the array, except for three of them (say $a,b,c$) which appear exactly once.
Can you give an $O(n)$ time and $O(1)$ space (assuming RAM model) algorithm to find out what the three unique integers $a,b,c$ are?
An easier version: Exactly two appear once in array of $2n+2$.
Easier than that: Exactly one appears once in array of $2n+1$.
[Please feel free to comment with your solution to any version of the problem]
[Solution]
for the 2N+1 problem:
ReplyDeleteXOR across all members of the array
The result is the unique element.
I don't yet see how to generalize this to 2N+2 or 2N+3
Collins
Ok... went for a walk and can now do the 2N+2
ReplyDeleteDo the XOR thing from 2N+1 the result is a XOR b
Since a and b are distinct the result is non-zero. Use its least significant 1 bit to partition the entire array in to two sub arrays (in place so as to stay O(1) ) Each sub array will contain pars plus either a or b (but not both since the differ at this bit position)
Now apply the 2N+1 procedure to each sub array
Seems like there must be a way to decompose 2N+3 into a 2N+2 and a 2N+1 but it has not occurred ot be yet since a XOR b XOR c could be 0. A method for guaranteeing that a particular bit that will distinguish a from b or from c is not clear to me yet
Your solutions to the 2N+1 and 2N+2 versions are correct. Well done!
Delete2N+3 is doable, but it is a little tricky.
Hi Collins,
DeleteI have posted a solution: http://ruffnsluff.blogspot.com/2014/12/solution-to-find-three-missing-numbers.html
I think median could be found in O(n) with O(1) space? If so we could use it to tackle 2N+2 & 2N+3.
ReplyDeleteMedian cannot be found in constant space linear time. I believe it has been shown that constant space would require $\Omega(n \log n)$ time.
Delete