3
$\begingroup$

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
$\endgroup$
2

1 Answer 1

3
$\begingroup$

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<i$ 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)$.

$\endgroup$
4
  • $\begingroup$ This is so clever, thank you! I'll try to implement it in code! $\endgroup$
    – Oskar
    Aug 13, 2021 at 15:48
  • $\begingroup$ @Oskar, its actually just a simple change from the well-known algorithm for the same question without the additional "flipping numbers" part :) $\endgroup$
    – nir shahar
    Aug 13, 2021 at 16:18
  • $\begingroup$ @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) $\endgroup$
    – nir shahar
    Sep 26, 2022 at 22:08
  • $\begingroup$ 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! $\endgroup$
    – ggorlen
    Sep 26, 2022 at 22:20

Your Answer

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

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