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.
