@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+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 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.
