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

Improve this question
$\endgroup$
3
  • $\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
    Commented Feb 15, 2016 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
    Commented Feb 15, 2016 at 18:03
  • $\begingroup$ cs.stackexchange.com/q/104817/755 $\endgroup$
    – D.W. ♦
    Commented Dec 1, 2019 at 1:58

1 Answer 1

Reset to default
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\}$.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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