We first compute the N^2 two sums, and sort the two sums. The for each TwoSum t, we check whether there is another two sum t' such that t.value + t'.value = target. The time complexity of this approach is O(N^2 logN)
On Wed, Jun 20, 2012 at 1:36 AM, rammar <[email protected]> wrote: > Lets see ur example... We can have two other arrays corresponding to our > n^2 array. > For every (target-arr[i]) which we search in our look up array, we can > also search the components which were used to get that sum. This can be > done in addition constant amount search. > I hope we can still go with Hemesh's algo. Please let me know if it breaks > somewhere... > > let's take a test case : > arr : 2 4 6 8 > arr[0] : 6 8 10 10 12 14 > arr[1] : 2 2 2 4 4 6 > arr[2] : 4 6 8 6 8 8 > > > P.S. Can we do better? > > On Wednesday, June 20, 2012 12:22:52 AM UTC+5:30, Amol Sharma wrote: >> >> @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 <[email protected]> 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 <[email protected]>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 <[email protected]> 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 < >>>>>>> [email protected]> 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 [email protected]. >>>>>>>> To unsubscribe from this group, send email to >>>>>>>> algogeeks+unsubscribe@**googlegr****oups.com<algogeeks%[email protected]> >>>>>>>> . >>>>>>>> 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/ >>>>>> **ms**g/algogeeks/-/9jCCN5iHDB8J<https://groups.google.com/d/msg/algogeeks/-/9jCCN5iHDB8J> >>>>>> . >>>>>> >>>>>> To post to this group, send email to [email protected]. >>>>>> To unsubscribe from this group, send email to algogeeks+unsubscribe@* >>>>>> *googlegr**oups.com <algogeeks%[email protected]>. >>>>>> 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 [email protected]. >>>>> To unsubscribe from this group, send email to algogeeks+unsubscribe@** >>>>> googlegr**oups.com <algogeeks%[email protected]>. >>>>> 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<https://groups.google.com/d/msg/algogeeks/-/SGN_A_YrZlkJ> >>> . >>> >>> To post to this group, send email to [email protected]. >>> To unsubscribe from this group, send email to algogeeks+unsubscribe@** >>> googlegroups.com <algogeeks%[email protected]>. >>> 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/-/eDvKXozaZV8J. > > To post to this group, send email to [email protected]. > To unsubscribe from this group, send email to > [email protected]. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- regards, Bhaskar Kushwaha Student CSE Third year M.N.N.I.T. Allahabad -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
