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/* >>>>> *msg/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@** >>>>> 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 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>. >>>> >>> >>> >>> >>> -- >>> 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 [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. >> > > -- 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.
