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.