CODEWITHSUNDEEP
algorithm
Dave Jones
Dave Jones

Reputation: 67

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

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: 2447

Answers (1)

Yonlif
Yonlif

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

Related Questions