[interesting question] find an element which is sum of two other elements

[George2]

--------------------------------------------------------------------------------

Hello everyone,


I am discussing with my friends about an interesting question about find the maximum element in a set, which is the sum of two other elements.

For example, in set [1, 2, 3, 5, 8, 10], the answer is 10 (10 = 8 + 2),
which is the maximum element we can find, and it is the sum of two
other elements (8 and 2) in the set.

Currently, I only have brute-force solution. Sorting the set, which takes O(nlgn) time, then enumerate them one by one to find whether two elements can sum up to the maximum element (if the most maximum element does not meet the condition, move to the second largest one), which takes O(n^2) time, so the total time complexity is O(n^2).

I am wondering whether any one have better ideas?


thanks in advance,
George

[Darryl]

Are we talking unique elements in the set or can there be duplicates?

Guess it doesn't matter, in either event, one optimization is to cut the set in half based on the highest value, in your case 10 would cut in half at 5 creating
[1, 2, 3] and [5,8] then you only pair up elements from the left with elements from the right. (if you allowed duplicated and had for instance 2 fives you'd have to make sure you split the fives since it's the middle number, one in each group)

[pianorain]

Isn't that still O(n^2)?

• Assume that a set is a set, not a multi-set.
• Let O be the original set of numbers. Let o be the largest element in set O.
• Let A be the set of numbers less than half of the largest element in O. Let a be an element of set A.
• Let B be the set of numbers greater than half of the largest element in O. Let b be an element of set B.
• The number of elements in O is equal to n. The number of elements in A is equal to xn, where x is less than 1. The number of elements in B is equal to (1-x)n.
• You have to traverse A and B a total of xn * (1-x)n times. That's a polynomial with degree of 2, hence O(n^2).

You can optimize it by starting at the smallest element in set B and the largest element in set A, traversing set A first. While traversing set A, if a + b is less than o, then you have to increment b to the next element of set B and start over in set A. However, I still think that's O(n^2).

[edit] Had to redefine a couple of variables.

[Darryl]

But it's still has to be more efficient because it's not even considering certain enumerations such as if 3+2 = 10 where the original idea did ( or at least that's how I understood it).