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 ?

New contributor
faeif is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
  • 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)$. – Apass.Jack Nov 8 at 20:20
  • @Apass.Jack i added an example – faeif Nov 8 at 20:47

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.

New contributor
ךאמיל is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.

Your Answer

faeif is a new contributor. Be nice, and check out our Code of Conduct.
 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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