Look out for Bentley Ottman Sweep line algorithm to determine all intersection points of set of line segments. The worst case running time is O(N^2 lg N) since max no of intersection points is O(N^2). But since we need to determine only one intersection, we can modify the algorithm to determine if
There are two more solutions.Let the common computer be called Master and others be called slaves.1. The master maintains a min-priority queue and asks for the smallest number from each slave. It then deques one number from the queue and asks for the next smallest number from the slave which origi
I think you are right on this point ... my reduction to the
element uniqueness problem is not perfect. Maybe there could exist a
better algorithm or maybe there is another way to reduce it to element
uniqueness. Maybe some one can come up with a faster way than O ( nlgn
) .
-DhyaneshOn 12/4/05, p
But Dhyanesh, don't forget the condition that we are given that exactly
one number is repeated twice. What you said is true for the general
case. How do you prove that for this special, there's no algorithm that
takes less than O(nlogn)? If such an algorithm exists and we give an
input consisting
I mentioned the range constraint of the algorithm previously (which I
guess you ignored), My assertions are that it can be used with
many sets of integers in the real world, and whenever it can be used,
it is very fast, indeed.
In academia, huge and negative numbers really have their place. In t
