2
$\begingroup$

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.

$\endgroup$
4
  • 3
    $\begingroup$ 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. $\endgroup$
    – marty cohen
    Jan 23, 2016 at 6:22
  • 1
    $\begingroup$ I think you can use radix sort since the range is bounded? $\endgroup$
    – Dan Brumleve
    Jan 23, 2016 at 6:29
  • $\begingroup$ 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. $\endgroup$
    – Dan Brumleve
    Jan 26, 2016 at 4:29
  • 2
    $\begingroup$ I suspect $A$ and $B$ are sorted when they are given to you and your approach is the desired answer. $\endgroup$
    – Ross Millikan
    Jan 26, 2016 at 5:08

2 Answers 2

Reset to default
1
$\begingroup$

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

$\endgroup$
5
  • 1
    $\begingroup$ How can you guarantee only a constant number of collisions in each hash bucket? $\endgroup$
    – Dan Brumleve
    Jan 23, 2016 at 6:38
  • 1
    $\begingroup$ 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$. $\endgroup$
    – Dan Simon
    Jan 23, 2016 at 6:51
  • $\begingroup$ Also we are looking for worst case not average case. What if all the numbers end up in the same bucket? $\endgroup$
    – Dan Brumleve
    Jan 23, 2016 at 6:57
  • $\begingroup$ 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)$. $\endgroup$
    – Dan Simon
    Jan 23, 2016 at 7:39
  • $\begingroup$ 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. $\endgroup$
    – Dan Brumleve
    Jan 23, 2016 at 20:38
0
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .