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$

Question

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.

Answer 1

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

Answer 2

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.