It would be nice if you can come up with an O(n) algorithm for that, but frankly, I dont think it is possible at all. Of course, if the numbers are all in O(n) and if we can afford O(n) additional space, we can go in for a counting sort like mechanism. Or else, if numbers are not in O(n), we have to sort and do what i said earlier.
So if the array is unsorted, we can get it done only in O(nlgn).
-Vijay
On 12/20/05, Hemanth <[EMAIL PROTECTED]> wrote:
Hi,
Let me try to slightly present the problem in a different way.
1. First go through the unsorted array and get two smaller arrays. One
array containing numbers <= z/2 and other array containing numbers >
z/2 and <= z. Other numbers obviously can be ignored.
2. Now 'z' complement(i.e. number = z - number) all the numbers in the
array which has numbers <= z/2.
3. The problem now is to find if any number in this complement array
repeats in the other array in O(n) time.
Am currently trying to find a solution to this.... will get back as
soon as I get an answer.
