# Describe an $O(N)$ time algorithm for determining if there is an integer in a sequence $A$ and an integer in a sequence $B$ such that $x = a + b$

Unfortunately I couldn't make the title for my question long and I didn't really know how to shorten it, so there are some added constraints:

Let $A$ and $B$ be two sequences of $n$ integers each, in the range $[1 \ldots n^4]$. Given an integer $x$, describe an $O(n)$-time algorithm for determining if there is an integer $a$ in $A$ and an integer $b$ in $B$ such that $x = a + b$.

I don't really know how to solve this in $O(N)$ time. The first thing I could think of was sorting both sequences $A$ and $B$ (which would take $O(n\log n)$ and then having $a$ be the first integer in sequence $A$ and $b$ be the last integer for sequence $B$. I could then check:

if(A[a] + B[b] < x) -> update index a to be a + 1
if(A[a] + B[b] > x) -> update index b to be b - 1
if(A[a] + B[b] = x) -> success


However, this algorithm is not $O(N)$ time. So, I'm wondering what kind of hint or trick would need to be used in order to solve this problem.

• My guess is that the solution would involve concatenating representations of the integers. The upper limit of $n^4$ is probably important. Also, in time $O(n)$ you can find the min and max of each sequence. Just throwing ideas out. Remember that free ideas are sometimes worth it. Say goodnight, Gracie. Jan 23, 2016 at 6:22
• I think you can use radix sort since the range is bounded? Jan 23, 2016 at 6:29
• Are $n$ and $N$ the same thing? I assumed so in my answer because you have used them interchangably but if $N$ means the total input size and $n$ means the length of the list then there is an easy answer. Jan 26, 2016 at 4:29
• I suspect $A$ and $B$ are sorted when they are given to you and your approach is the desired answer. Jan 26, 2016 at 5:08

Allocate a hash map $H$. For each $a \in A$, set $H[x - a]$ to 1. Then, for each $b \in B$, if $H[b]$ is 1, you are done. Hash maps are $O(1)$ and worst case you traverse each list once, so the algorithm is $O(n)$.

• How can you guarantee only a constant number of collisions in each hash bucket? Jan 23, 2016 at 6:38
• Excellent question, I hadn't thought of that. I think at that point you'd have to do something clever that takes advantage of the $n^4$ range of values. For small enough $n$ (or assuming a computer with infinite memory), you could just use a $n^4$ sized array. Otherwise I suspect max number of collisions can be made constant using an appropriate hashing function based on $n$. Jan 23, 2016 at 6:51
• Also we are looking for worst case not average case. What if all the numbers end up in the same bucket? Jan 23, 2016 at 6:57
• Yes, I think a radix-sort-like approach like you mention in the comments could work. You can do it with nested hash maps, but now that I think about it, I think it would be easier to just create a Trie structure out of the digits of all the $x - a$ and traverse it with each $b$. Both building the trie and traversing it for all $B$ are $O(n)$. Jan 23, 2016 at 7:39
• I think we're to assume a model where arithmetic operations are constant. But there are $O(n \cdot \log{n})$ total digits, so we don't have enough time to inspect them all which would be required for the trie approach. I'm still not really sure about the radix sort idea. Jan 23, 2016 at 20:38

Let's simplify the problem, like how Dan Simon does in his answer: subtract each element of $A$ from $x$ and call the resulting set $A'$. Now the original problem is equivalent to $A' \cap B \ne \emptyset$, and also $\vert A' \cup B \vert \lt 2 \cdot n$.

A straightforward way to present this problem is as a list of $2\cdot n$ words of size $w = \lceil 1 + 4 \cdot \log_2{n} \rceil = O(\log{n})$. But this means the radix sort idea I mentioned cannot work in $O(n)$ since radix sort is $O(n \cdot w) = O(n \cdot \log{n})$. Nor can any method that operates on every bit or digit of the input numbers since there are $O(n \cdot \log{n})$ of them.

Maybe it is possible somehow without looking at every digit, given that we can perform arithmetic operations on entire words in constant time, so this is not a complete answer. But I cannot figure out how it might be done.