@hemesh :- please explain your approach 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@** >>>> 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/-/9jCCN5iHDB8J. >> >> 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. > -- Utsav Sharma, NIT 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.
