step 1: Sort array in place. Lets call it A. (N log N) step 2: Create two additional copies of array, lets call them B and C. (this is just for explanation, we can operate on same array A).
step 3: Take first element from array A. lets say its value is X. Find pair from B and C whose sum is nearest to -X. This step of finding pair is similar to Binary Search as array is sorted. step 4: Repeat step 3 for entire array A. On Mon, May 17, 2010 at 9:58 PM, Anurag Sharma <anuragvic...@gmail.com>wrote: > oops! > > Anurag Sharma > > > On Mon, May 17, 2010 at 5:00 PM, Navin Naidu <navinmna...@gmail.com>wrote: > >> @anurag: >> >> -99 -2 -1 3 +99 >> >> The min sum (=0) for value pair (-99, 99) >> >> Now skip, +99 and -99, so -1 will be selected: (99, -99, -1) = -1 >> >> Actual result: -2, -1, 3 : 0 >> >> >> >> >> >> On Mon, May 17, 2010 at 8:48 AM, Anurag Sharma <anuragvic...@gmail.com>wrote: >> >>> @Navin : Let me work out the case you gave me array={-99,0,2,-1,99} >>> >>> 1. Sort the array in nlogn time: array={-99,-1,0,2,99} >>> >>> 2. consider all possible pairs of numbers and keep track of the sum >>> closest 2 zero: >>> -99+-1=-100, |-100|=100 >>> -99+0=-99,|-99|=99 >>> -99+2=-97,|-97|=97 >>> -99+99=0,|0|=0 <------- this is the minimum sum(=0) for value pair >>> (-99, 99) >>> -1+0=-1,|-1|=1 >>> -1+2=1,|1|=1 >>> -1+99=98,|98|=98 >>> 0+2=2,|2|=2 >>> 0+99=99,|99|=99 >>> 2+99=101,|101|=101 >>> >>> >>> 3. Now traversing the array skipping the values -99, 99 and trying to get >>> minimum sum after including it in the existing sum : >>> array={-99,-1,0,2,99} >>> take -99: skip >>> take -1: 0+-1= -1 and |-1|=1 >>> take 0: 0+0=0 and |0|=0 <---- this is the minimum so the third number >>> is 0 >>> take 2: 0+2=2 and |2|=2 >>> take 99: skip >>> >>> this way we got the three numbers as -99,99 and 0. Were you expecting >>> some other combo? >>> In step 3 we can skip checking the rest of the elements when we find the >>> sum increasing as the array is already sorted. >>> >>> Let me know if there is still some issue in it. >>> >>> >>> Regards, >>> >>> Anurag Sharma >>> >>> >>> >>> On Sun, May 16, 2010 at 9:26 PM, Navin Naidu <navinmna...@gmail.com>wrote: >>> >>>> >>>> @anurag: wont work, consider the following case: -99 0 2 -1 99 >>>> >>>> >>>> >>>> >>>> >>>> On Sun, May 16, 2010 at 9:12 PM, Rohit Saraf < >>>> rohit.kumar.sa...@gmail.com> wrote: >>>> >>>>> @anurag : won't work >>>>> -------------------------------------------------- >>>>> Rohit Saraf >>>>> Second Year Undergraduate, >>>>> Dept. of Computer Science and Engineering >>>>> IIT Bombay >>>>> http://www.cse.iitb.ac.in/~rohitfeb14<http://www.cse.iitb.ac.in/%7Erohitfeb14> >>>>> >>>>> >>>>> >>>>> >>>>> -- >>>>> 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. >>>>> >>>> >>>> >>>> >>>> -- >>>> Thanks & Regards, >>>> >>>> - NMN >>>> >>>> -- >>>> 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<algogeeks%2bunsubscr...@googlegroups.com> >>> . >>> For more options, visit this group at >>> http://groups.google.com/group/algogeeks?hl=en. >>> >> >> >> >> -- >> Thanks & Regards, >> >> - NMN >> >> -- >> 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<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.