Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

How to find all sums of two sets in O(nlogn) time (arithmetic and comparisons)

Tags:

algorithm

If sets A, B are subsets of {1, ..., n}, how would I find all elements of the set {a + b: a ∈ A, b ∈ B} in O(nlogn) time (arithmetic and comparisons)?

like image 527
Dave Jones Avatar asked Dec 13 '22 10:12

Dave Jones


1 Answers

This question has a classic solution using FFT.

FFT stands for Fast Fourier transform but can be used in order to multiply two polynomials in O(n log n) where n = max length (Highest power).

Let's create two polynomials from sets A and B, each will be the sum of x to the power of an element in the set, ∑ x^a | a ∈ A.
Now multiply these two using FFT in O(n log n) time since each polynomial highest power can't exceed n.

The powers of the new polynomial are exactly the new set! Since x^a * x^b == x^(a+b).

like image 71
Yonlif Avatar answered May 24 '23 12:05

Yonlif