# Find if two elements in an array sum up to a given number

I'm currently solving some problems over at kattis, in particular the Add 'Em Up task.

A quick summarizing:

You are given an array with $$1 \leq n \leq 100000$$ elements and an integer $$2 \leq s \leq 200 000000$$. You want if there exists two elements $$x_i,x_j, i \neq j,$$ in the array such that $$x_i + x_j = s$$. However, there's a twist that you can flip certain numbers to obtain a new number. For example, if $$x_i = 51$$ then a flip would yield $$\bar{x}_i = 15.$$ Still, you can just use an element once, so $$x_i + \bar{x}_i = s$$ is not an accepted answer.

Looking at the worst case scenario, our new array would contain $$2n$$ elements, $$\{x_1, ..., x_n, \bar{x}_1, ..., \bar{x}_n \}.$$

I've written an algorithm that works, but it's not efficient enough. I believe it's $$\in O(n^2)$$.

If $$N = \{x_1, ..., x_n, \bar{x}_1, ..., \bar{x}_n \}$$, and if $$x_i$$ doesn't have a flip, then $$\bar{x}_i =$$ 'NF'. (NoFlip, str).

for i in range(2*n) do
for j in range(2*n) do
if (j-i) % n != 0 and N[i], N[j] != 'NF':
if N[i] + N[j] == S:
return True

return False



How can I make the code more efficient?

I've tried:

• Removed all elements $$\geq S$$ first
• Sort. After duplicating the numbers by flipping as you suggest, we are back to an old question: Checking if there are 2 elements in an array that sum to X in O(n lg n) Aug 13, 2021 at 14:09
• (You want if there exists two elements… seems to lack a word as well as use the wrong numerus.) Aug 14, 2021 at 10:00

There is an $$O(n)$$ solution, using a nice trick:

Keep track of the different values you have already seen in an auxiliary hashmap, called $$seen$$.

Now, loop over the elemnts of the array (the original array, you don't have to add the negations), and for each $$x_i$$ do the following:

1. If either $$s-x_i\in seen$$ or $$s-\overline{x_i}\in seen$$, then return $$True$$.
2. Else, add both $$x_i,\overline{x_i}$$ to $$seen$$, and continue to the next element in the list.

You will see that if for any $$i$$ we get that $$s-x_i\in seen$$ before we added $$x_i$$ at the $$i$$'th iteration, then there must be some $$j< i$$ such that $$x_i+x_j=s$$ or $$x_i+\overline{x_j}=s$$. And for a similar reason, if $$s-\overline{x_i}\in seen$$ before we added it in the $$i$$'th iteration, then there must be some $$j with $$\overline{x_i}+x_j=s$$ or $$\overline{x_i}+\overline{x_j}=s$$.

Thechnically speaking, the solution works in $$O(n^2)$$ in the worst case, but since we deal with a hash map, we can say that on average (or at least, its very likely) that it will run in $$O(n)$$.

• This is so clever, thank you! I'll try to implement it in code! Aug 13, 2021 at 15:48
• @Oskar, its actually just a simple change from the well-known algorithm for the same question without the additional "flipping numbers" part :) Aug 13, 2021 at 16:18
• @ggorlen thanks for pointing this out! Seems I misunderstood what "flip a number" meant, and now I fixed the answer. However, I still don't see why you can use a simple array for lookup instead of a hash, considering we don't know in what range the numbers live in (or if they are even natural numbers). From the link in the question - seems that they are integers bounded by a huge number (which is there just for practical purposes, so we can treat is as unbounded) Sep 26, 2022 at 22:08
• Yeah, theoretically it could be unbounded but in the problem description. the upper bound on the numbers is 100,000,000. For posterity, I'll leave a link to my explanation but I removed my outdated comments since the edit resolves them. Thanks! Sep 26, 2022 at 22:20