@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 <[email protected]>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 <[email protected]>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 <
>> [email protected]> 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 <[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.
>>>
>>
>> --
>> 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.
>>
>
> --
> 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.
>
--
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.
