slight change to the first algorithm.. if the element doesn't exist, then at
the end of the binary search, we'd have to look at the element on the left,
current, and right to see which one gives the closest result.
On 15 May 2010 16:35, divya jain <sweetdivya....@gmail.com> wrote:
> 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.
