Cant it be done this way:- 1. Sort the array in O(n log(n)) time 2. select all pairs of numbers in array and keep track of minimum sum (closest to zero) and also their indices, in O(n^2) time 3. In another iteration skipping the indices which gave the minimum sum, check whether the current number yields the sum closest to zero. Thats what your third number is.
It takes n log(n) + n^2 + n time which is O(n^2) and O(1) extra memory Correct me if I am wrong. Anurag Sharma http://anuragsharma-sun.blogspot.com/ On Mon, May 3, 2010 at 6:18 PM, jalaj jaiswal <jalaj.jaiswa...@gmail.com>wrote: > > given an array(unsorted) may contain negative numbers too > find the index of three numbers whose sum is closest to zero in O(N2 log > N) time and O(N) space. > > P.S -3 is more close to zero then -6 (number line ...) > > -- > With Regards, > Jalaj Jaiswal > +919026283397 > B.TECH IT > IIIT ALLAHABAD > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algoge...@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com> > . > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
