2
$\begingroup$

It is required to count number of unordered pairs in an array of size n ,

l[i]+l[j] = 2*l[k] , where 1<=i< j<=n and 1<=k<= n

My Approach:

l = [1,3,5,4,2,5]
l.sort() 
l2 = [] 
for i in l:
    l2.append(2*i) 
count = 0 
for combo in combinations(l, 2):
    if sum(combo) in l2:
        count+=1 

print(count) # count comes out to be 7

Please help in reducing Time Complexity O(n^2) to less if possible. Space Complexity is not a problem.

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ This is essentially the 3SUM problem. Look it up and you'll see how to solve this in quadratic or almost quadratic time. It is conjectured that you can't do substantially better than quadratic time. $\endgroup$ Commented Apr 7, 2018 at 12:26
  • $\begingroup$ But 3Sum problem also get solved in O(n^2) time only. $\endgroup$ Commented Apr 7, 2018 at 12:35
  • 1
    $\begingroup$ Your current algorithm is $\Theta(n^3)$ in the worst case (since you're not using binary search to search l2). Your problem is very likely 3SUM-hard, so it is conjectured that it has no $O(n^{2-\epsilon})$ algorithm for any positive $\epsilon$. $\endgroup$ Commented Apr 7, 2018 at 12:38

1 Answer 1

Reset to default
2
$\begingroup$

Your problem (more accurately, the problem of deciding whether there is any solution) is 3SUM-complete. This can be shown in essentially the same way that the two main variants 3SUM and 3SUM' are shown to be equivalent (check the original paper of Gajentaan and Overmars, for example). Therefore it has an $O(n^2)$ algorithm, but it is conjectured that there is no $O(n^{2-\delta})$ algorithm for any $\delta > 0$.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.