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)?
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)
.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With