0
$\begingroup$

This question already has an answer here:

Suppose we have $n$ different summands. Is it possible to get the sum x with a maximum of two of the $n$ summands (Below the m summands there can be several times the same one). For example you have the summands (2,4,6,7). So its possible to get the sum $2+4 =6$,$6=6$ but its impossible to get the sum $3$ or $1$ ect.

My idea of an algorithm would have the runtime $\mathcal{O}(n\log(n))$. Now I'm not sure if this is already aymptotically optimal ?

$\endgroup$

marked as duplicate by Yuval Filmus algorithms Dec 9 '18 at 1:17

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ Not sure what you are asking. Is the sum of the two largest summands the maximum you wanted? You can find those two in $O(n)$. $\endgroup$ – Apass.Jack Nov 8 '18 at 20:20
  • $\begingroup$ @Apass.Jack i added an example $\endgroup$ – faeif Nov 8 '18 at 20:47
0
$\begingroup$

If the numbers have a limit on their value, i.e. all numbers are smaller than $m$, then you can get runtime of $O(n + m)$: in an array $t$ of size $m$, for each number $a$ in the set of summands, check if $t[x - a] > 0$: if yes, then the answer is $(a, x - a)$. If not, set $t[a] = 1$ and continue with the next number.

This can be slightly improved with assigning values in buckets, but the worst time complexity will be $O(nm)$.

Otherwise, $O(n \log n)$ is the optimal complexity.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.