[algogeeks] Re: Finding duplicate

[Dhyanesh]

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 ) .

-Dhyanesh

On 12/4/05, pramod <[EMAIL PROTECTED]> wrote:

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 of several repititions (or no repititions at all), it
might give us wrong result since the pre-condition of running the algo
has failed. Let me explain to you this way:
input --> Algo --> output
Here input must satisfy the condition that exactly one number is
repeated twice, in which case, Algo guarantees that output will consist
of the two indices of that repeated number.
But if we give input not satisfying this condition, Algo is not liable
work correctly and it can and might give wrong results.
Let me know your thoughts on this.