Reputation: 67
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)?
Upvotes: 5
Views: 2445
Reputation: 1800
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)
.
Upvotes: 13