Let $A$ and $B$ be ordered (ascending) sets of integers, and let $x \in Z$. Design an efficient algorithm (in # of steps) for computing the number of different ways an element of $A$ can be summed with an element of $B$ such that their sum is less than or equal to $x$. Set elements may be in the order of $10^{12}$.
$\begingroup$
$\endgroup$
Add a comment
|
$\begingroup$
$\endgroup$
Fix $b$ to be the least element of $B$, then perform binary search over $A$ in order to find the greatest element of $A$, lets call it $a$, such that $a + b \leq Z$. Having found such element and its index $i$, we can be sure for all elements $a' \in A, a' < a, a' + b \leq Z$. Thus, we have $i$ ($i+1$, if the index starts at $0$) solutions with $b$. Now select the successor of $b$, and perform the same binary search over $A$. This will yield $i_{2}$ new solutions. You can do this until you find an element of $B$ whose sum with the first element of $A$ is greater than $Z$. The algorithm that follows such steps should do so in about $\mathcal{O}(log(\lvert A\rvert$)|B|)
