Very simple N^2*logN solution: sort the input array, then go through all
pairs Ai, Aj (N^2 time), and for each pair check whether (S - Ai - Aj) is in
array (logN time).
On 12 May 2010 23:08, jalaj jaiswal <jalaj.jaiswa...@gmail.com> wrote:
> @sateesh
> suppose after sorting the array is
> -99,-98,-97,-96,-95,-2,-1,0,4,5,99
>
> the answer should be {-99,0,99}.. sum is closest to zero here....
> so i dnt think the transition method works
>
>
>
>
>
>
>
>
>
>
> On Fri, May 7, 2010 at 9:58 PM, sateesh <sateeshk...@gmail.com> wrote:
>
>> I think this can be solved in better way.
>>
>> 1) Store the copy of array to get the indexes for the elements at the
>> end of algo
>> 2) Sort the array time: O(nlogn), space: O(1)
>> 3) If first element of array is -ve and last element of array is not -
>> ve, find the element at
>> which -ve to +ve transition happens
>> ex: -a -b +c +d
>> check the absolute minimum of following combinations and pick
>> the correct pair
>> -b+c+d
>> -a+c+d
>> -a-b+c
>> -a-b+d
>> here I assumed two +ve, two -ve. If only one -ve or one +v
>> exists, we can pick the correct 3 elements straight away
>> else if all are -ve numbers , pick last 3 elements
>> else pick first 3 elements
>>
>> This total process takes O(n) time
>> 4) Based on picked three elements, do linear search on copied array
>> to get there indexes.
>> time: O(n)
>>
>> Overall it takes O(nlogn) time complexity and O(n) space complexity.
>>
>> Do you guys find any flaw in it ?
>>
>> -Sateesh
>> IIT Kanpur 2004 M.Tech CSE Batch.
>>
>>
>>
>>
>>
>> On May 4, 10:43 pm, Afroz Mohiuddin <afrozena...@gmail.com> wrote:
>> > Well if you want a sum of exactly 0 (or any constant) , there is an
>> O(N^2)
>> > way
>> >
>> > Take your array, and hash it, note that it is always possible to hash a
>> > static set of keys so that the search/find in it is worst case O(1).
>> This
>> > takes O(N) space, and time.
>> >
>> > Then over all the tuples of numbers in the original array (a,b) check if
>> 0 -
>> > (a+b) is there in the hash set, time complexity O(N*N).
>> >
>> > For closest to 0 I guess the above solution is good.
>> >
>> > On Mon, May 3, 2010 at 2: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>
>> <algogeeks%2bunsubscr...@googlegroups.com<algogeeks%252bunsubscr...@googlegroups.com>
>> >
>> > > .
>> > > For more options, visit this group at
>> > >http://groups.google.com/group/algogeeks?hl=en.
>> >
>> > --
>> > We are here on earth to do good for others. What the others are here
>> for, I
>> > don't know.
>> >
>> > Afroz Mohiuddin
>> > Final Year Masters Student
>> > Dept Computer Science and Engineering
>> > Indian Institute of Technology Kanpur
>> > Kanpur - 208016
>> > INDIA
>> >
>> > --
>> > 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 athttp://
>> 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.
>>
>>
>
>
> --
> 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.
