@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.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
