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 Ω(nlogn) time.
Delete