@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@**
>>>>> 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/-/9jCCN5iHDB8J.
>>>
>>> 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.
>>
>
>
>
> --
> 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.
