3
$\begingroup$

Let A and B be two finite non-empty sets of positive integers. Their sumset is the set of all possible sums a + b where a is from A and b is from B. For example, if A = {1, 2} and B = {2, 3, 6} then A + B = {1 + 2, 1 + 3, 1 + 6, 2 + 2, 2 + 3, 2 + 6} = {3, 4, 5, 7, 8}.

As we can see, cardinality #(A + B) is less than sum of cardinalities #A + #B. So i wonder whether we can calculate #(A+B) faster than just calculating all #A + #B sums and inserting them in some set-like data structure.

I've tried searching "sumset cardinality algorithm" and so on but didn't succeed.

P.S. We may assume that there is some constan K, not very lare - for example 10^5, such that 1 <= #A, #B <= K and all the elements of A and B are between 1 and K

$\endgroup$
  • $\begingroup$ What is the use? Are the sets large? Same size, or is one substantially smaller than the other one? What is the smallest/largest value in the sets (i.e., is the largest element much larger than the size of the set)? In any case, if the obvious algorithm is fast enough, don't spend too much time on this. Even though it is an intriguing problem ;-) $\endgroup$ – vonbrand Feb 15 '16 at 17:36
  • 1
    $\begingroup$ @vonbrand Well, i'm interested in the general case. But originally it was a programming competition problem with limitations 1 <= #A, #B <= 10^5. Since the time given is 1 second and there are approximately 10^10 pairs to consider, brute force is no use. $\endgroup$ – Igor Feb 15 '16 at 18:03
0
$\begingroup$

Use the FFT. The characteristic vector of $A+B$ is the convolution of the characteristic vectors for $A$ and for $B$. Convolutions can be computed efficiently using a FFT. As long as every element of $A,B$ is not too large, this will be efficient: the running time will be approximately $O(n \lg n)$ if $A,B \subseteq \{1,2,\dots,n\}$.

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