1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.