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)?
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).
Related