@rammar: can you please explain the case...which i took in the earlier post..with this method.
-- Amol Sharma Final Year Student Computer Science and Engineering MNNIT Allahabad <http://gplus.to/amolsharma99> <http://twitter.com/amolsharma99><http://in.linkedin.com/pub/amol-sharma/21/79b/507><http://www.simplyamol.blogspot.com/><http://facebook.com/amolsharma99> On Tue, Jun 19, 2012 at 11:27 PM, rammar <getam...@gmail.com> wrote: > @Hemesh +1 > > Please correct me if i am wrong. > Creation of our look up array a[n*n] -> sum of all the pairs will take > O(n^2). > Search using binary sort or quick sort in O(n^2 log (n^2) ) == O(n^2 > log n) > We will traverse this array, and for every element we will find (target > - a[i]) -> This traversal will again take O(n^2). > For every (target -a[i]) we will search it in our lookup > array using binary search -> This will take O(log n^2) = O(2log n) = O(log > n) > We will store all the matched for the target. > > Final complexity = O(n^2) + O(n^2 log n) + O(n^2)*O(log n) == O (n^2 log > n) > If the values of max of a[n] is not very high, we can go with a hash > map. This will result in a quick look up. And we can get the answer in > O(n^2). > > > P.S. Can we do better? > > > On Monday, June 18, 2012 6:10:33 PM UTC+5:30, Jalaj wrote: >> >> @KK and hemesh >> target is not a constant value , it can be any element in array , so you >> need to do binary search for all (array[i] - (a+b)) to find which increases >> the complexity to n^3logn. >> So, i think the n^3 approach which i gave before do it ?? >> >> ------ Correct me if m wrong >> >> On Mon, Jun 18, 2012 at 2:58 PM, Amol Sharma <amolsharm...@gmail.com>wrote: >> >>> @hemesh,kk: >>> >>> let's take a test case : >>> arr : 2 4 6 8 >>> arr^2 : 6 8 10 10 12 14 (sum of each unique pair in >>> arr[i]) >>> >>> let's say target sum is 26 >>> >>> your solution will return true as they 12+14=26 but in 12 and 14, 8 is >>> common, infact 26 is not possible in the given array >>> >>> can u please elaborate how will you take care of such situation ? >>> >>> @jalaj: >>> yes it's O( (n^3)*logn) >>> >>> @bhavesh: >>> fyi.. >>> log(n^3)=3*log(n)=O(log(n)) >>> so it's same.. :P >>> >>> >>> >>> >>> >>> -- >>> >>> >>> Amol Sharma >>> Final Year Student >>> Computer Science and Engineering >>> MNNIT Allahabad >>> >>> <http://gplus.to/amolsharma99> >>> <http://twitter.com/amolsharma99><http://in.linkedin.com/pub/amol-sharma/21/79b/507><http://www.simplyamol.blogspot.com/><http://facebook.com/amolsharma99> >>> >>> >>> >>> >>> >>> >>> On Mon, Jun 18, 2012 at 12:29 AM, KK <kunalkapadi...@gmail.com> wrote: >>> >>>> @Hemesh : +1 >>>> @Jalaj : read Hemesh's solution again it is for 4sum. >>>> In short, make a new array having sum of each unique pair of given >>>> array. -> O(n^2) >>>> sort it -> O(n^2) >>>> for each number bi in new array, binary search (target - bi) in the >>>> same array -> O(n^2) >>>> >>>> >>>> On Sunday, 17 June 2012 12:41:40 UTC+5:30, Jalaj wrote: >>>>> >>>>> The solution which hemesh gave was solution to 3SUM hard problem the >>>>> best solution for which can be achieved in n^2 . >>>>> And the original question is a kind of 4SUM hard problem for which >>>>> best possible solution i think is again n^3 and Amol what you told is not >>>>> n^3 , finding all triplets will itself take n^3 and doing a binary search >>>>> again that sums upto n^3*logn. >>>>> >>>>> @shashank it is not a variation of 3SUM problem as in 3SUM problem >>>>> a+b+c = some constant , but in your case it is "b+c+d = s-a", where a can >>>>> change again and again so if you do even apply 3SUM logic to it you will >>>>> have to do it for every a which will make it n^2*n = n^3 >>>>> >>>>> >>>>> >>>>> On Sat, Jun 16, 2012 at 2:45 AM, sanjay pandey < >>>>> sanjaypandey...@gmail.com> wrote: >>>>> >>>>>> @hemesh cud u plz elaborate wat is b[k]=a[i]+a[j]...n also ur >>>>>> solution... >>>>>> >>>>>> -- >>>>>> You received this message because you are subscribed to the Google >>>>>> Groups "Algorithm Geeks" group. >>>>>> To post to this group, send email to algogeeks@googlegroups.com. >>>>>> To unsubscribe from this group, send email to algogeeks+unsubscribe@* >>>>>> *googlegr**oups.com <algogeeks%2bunsubscr...@googlegroups.com>. >>>>>> For more options, visit this group at http://groups.google.com/** >>>>>> group**/algogeeks?hl=en<http://groups.google.com/group/algogeeks?hl=en> >>>>>> . >>>>>> >>>>> >>>>> >>>>> >>>>> >>>>> -- >>>> You received this message because you are subscribed to the Google >>>> Groups "Algorithm Geeks" group. >>>> To view this discussion on the web visit https://groups.google.com/d/** >>>> msg/algogeeks/-/9jCCN5iHDB8J<https://groups.google.com/d/msg/algogeeks/-/9jCCN5iHDB8J> >>>> . >>>> >>>> To post to this group, send email to algogeeks@googlegroups.com. >>>> To unsubscribe from this group, send email to algogeeks+unsubscribe@** >>>> googlegroups.com <algogeeks%2bunsubscr...@googlegroups.com>. >>>> For more options, visit this group at http://groups.google.com/** >>>> group/algogeeks?hl=en <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 algogeeks@googlegroups.com. >>> To unsubscribe from this group, send email to algogeeks+unsubscribe@** >>> googlegroups.com <algogeeks%2bunsubscr...@googlegroups.com>. >>> For more options, visit this group at http://groups.google.com/** >>> group/algogeeks?hl=en <http://groups.google.com/group/algogeeks?hl=en>. >>> >> >> >> >> -- >> Regards, >> >> Jalaj Jaiswal >> Software Engineer, >> Zynga Inc >> +91-9019947895 >> * >> * >> FACEBOOK <http://www.facebook.com/jalaj.jaiswal89> >> LINKEDIN<http://www.linkedin.com/profile/view?id=34803280&trk=tab_pro> >> >> -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To view this discussion on the web visit > https://groups.google.com/d/msg/algogeeks/-/SGN_A_YrZlkJ. > > To post to this group, send email to algogeeks@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. > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@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.
