Hello everyone!

While solving a math problem recently, I came up with an interesting trick on sets union. The ordinary solution using inclusion-exclusion principle for 3 sets looks as following:

|x1 ∪ x2 ∪ x3| = |x1| + |x2| + |x3| — (|x1 ∩ x2| + |x1 ∩ x3| + |x2 ∩ x3|) + |x1 ∩ x2 ∩ x3|

Obviously the time complexity to compute union of N sets by this approach is O(2 ^ N).

Now, lets store for each set xi (1 <= i <= N) only those subsets that are not intersected with other subsets on prefix:

u1 = x1

u2 = |x2| — |x2 ∩ u1|

u3 = |x3| — |x3 ∩ u2| — |x3 ∩ u1|

Then answer could be found as following:

|x1 ∪ x2 ∪ x3| = |u1| + |u2| + |u3|

The algorithm is simplified to O(N ^ 2).

But, we can reorder the formula to compute each ui as following:

u3 = |x3| — |x3 ∩ |u1 ∪ u2||

u4 = |x4| — |x4 ∩ |u1 ∪ u2 ∪ u3||

...

Here we only need to maintain the union of previous subsets on prefix, that could be done in O(1) since they do not intersect.

Thus total complexity to find union of N sets is reduced to O(N).