@ Amol Sharma thanx got it..
yup, overlooked those case's :-) my bad.. On Sat, Jun 23, 2012 at 1:31 PM, Amol Sharma <amolsharm...@gmail.com> wrote: > @sourabh: > for this particular question.. > in your code replace > > if(binary_search(c,c+size,-b[i])) > count++; > > by > > count+=upper_bound(c,c+size,-b[i])-lower_bound(c,c+size,-b[i]); > > you are actually missing some of the quadruples....as there can be more > than one element with value -b[i] in the array c and you are actually > ignoring them. > -- > > > 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 Sun, Jun 24, 2012 at 1:22 AM, Sourabh Singh > <singhsourab...@gmail.com>wrote: > >> @ALL >> >> O(n^2 lg(n^2)) >> >> http://www.spoj.pl/problems/SUMFOUR/ >> >> my code : >> http://ideone.com/kAPNB >> >> plz. suggest some test case's : >> >> On Sat, Jun 23, 2012 at 6:59 AM, Amol Sharma <amolsharm...@gmail.com>wrote: >> >>> @bhaskar,rammar: >>> >>> I don't think your algo willn not work for the following test case -- >>> >>> >>> 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 >>> >>> -- >>> >>> >>> 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 Fri, Jun 22, 2012 at 11:45 PM, Bhaskar Kushwaha < >>> bhaskar.kushwaha2...@gmail.com> wrote: >>> >>>> 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 <getam...@gmail.com> 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 <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/**ms**g/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@**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 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> >>>>>>>>> . >>>>>>>>> >>>>>>>> >>>>>>>> >>>>>>>> >>>>>>>> -- >>>>>>>> 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 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 view this discussion on the web visit >>>>> https://groups.google.com/d/msg/algogeeks/-/eDvKXozaZV8J. >>>>> >>>>> 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. >>>>> >>>> >>>> >>>> >>>> -- >>>> 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 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. >>> >> >> -- >> 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. >> > > -- > 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. > -- 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.
