Inclusion-Exclusion

Consider LeetCode 878. Nth Magical Number: given two positive integers a and b, find the n-th positive integer that is divisible by a or b. For small n you could iterate through every integer and check, but n can be up to $10^9$, so brute force is hopeless. The key insight is a counting formula from combinatorics called the inclusion-exclusion principle, combined with binary search on the answer.

The core principle

If A is the set of multiples of a and B is the set of multiples of b, then the set of numbers divisible by a or b is $A \cup B$. The inclusion-exclusion principle says:

$$|A \cup B| = |A| + |B| - |A \cap B|$$

Why subtract $|A \cap B|$? Because numbers divisible by both a and b get counted once in $|A|$ and once in $|B|$, so we have double-counted them. Subtracting the intersection corrects for that.

What are the numbers divisible by both a and b? They are exactly the multiples of $\text{lcm}(a, b)$, the least common multiple. And $\text{lcm}(a, b) = a \cdot b / \gcd(a, b)$.

So the count of positive integers up to x that are divisible by a or b is:

$$\text{count}(x) = \lfloor x/a \rfloor + \lfloor x/b \rfloor - \lfloor x/\text{lcm}(a,b) \rfloor$$

Walking through a concrete example

Let a = 2, b = 3, and n = 4. We want the 4th number divisible by 2 or 3.

The sequence is: 2, 3, 4, 6, 8, 9, 10, 12, ... so the answer is 6.

First, $\text{lcm}(2, 3) = 6$. Now let us evaluate the counting function at a few values:

• $\text{count}(5) = \lfloor 5/2 \rfloor + \lfloor 5/3 \rfloor - \lfloor 5/6 \rfloor = 2 + 1 - 0 = 3$. Only 3 magical numbers up to 5 (they are 2, 3, 4). Not enough.
• $\text{count}(6) = \lfloor 6/2 \rfloor + \lfloor 6/3 \rfloor - \lfloor 6/6 \rfloor = 3 + 2 - 1 = 4$. Exactly 4. The 4th magical number is at most 6.

Notice the subtraction in action: 6 is divisible by both 2 and 3, so without the $- \lfloor 6/6 \rfloor$ correction, we would have counted it twice and gotten 5 instead of 4.

Combining with binary search

The counting function $\text{count}(x)$ is non-decreasing: as x grows, the count can only stay the same or increase. This monotonicity means we can binary search for the smallest x where $\text{count}(x) \geq n$.

The search bounds are straightforward. The answer is at least $\min(a, b)$ (the first magical number) and at most $n \cdot \min(a, b)$ (if every magical number were a multiple of the smaller value, the n-th one would be at most this). In practice, using lo = 1 and hi = n * min(a, b) works fine.

The code for LeetCode 878

from math import gcd

def nthMagicalNumber(n, a, b):
    MOD = 10**9 + 7
    lcm = a * b // gcd(a, b)

    lo, hi = 1, n * min(a, b)
    while lo < hi:
        mid = (lo + hi) // 2
        count = mid // a + mid // b - mid // lcm
        if count >= n:
            hi = mid
        else:
            lo = mid + 1
    return lo % MOD

The binary search finds the smallest x with at least n multiples of a or b up to x. Each iteration computes the count in $O(1)$ using our inclusion-exclusion formula.

Three-set inclusion-exclusion: LeetCode 1201

LeetCode 1201. Ugly Number III generalizes the idea: find the n-th positive integer divisible by a, b, or c. Now we have three sets, and the inclusion-exclusion formula extends to:

$$|A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C|$$

The logic is the same. Adding the individual sets overcounts pairwise overlaps, so we subtract those. But then we have subtracted the triple overlap too many times (it was added 3 times and subtracted 3 times), so we add it back once.

In terms of our counting function:

$$\text{count}(x) = \lfloor x/a \rfloor + \lfloor x/b \rfloor + \lfloor x/c \rfloor - \lfloor x/\text{lcm}(a,b) \rfloor - \lfloor x/\text{lcm}(a,c) \rfloor - \lfloor x/\text{lcm}(b,c) \rfloor + \lfloor x/\text{lcm}(a,b,c) \rfloor$$

where $\text{lcm}(a,b,c) = \text{lcm}(\text{lcm}(a,b), c)$.

The code for LeetCode 1201

from math import gcd

def nthUglyNumber(n, a, b, c):
    def lcm(x, y):
        return x * y // gcd(x, y)

    ab = lcm(a, b)
    ac = lcm(a, c)
    bc = lcm(b, c)
    abc = lcm(ab, c)

    lo, hi = 1, n * min(a, b, c)
    while lo < hi:
        mid = (lo + hi) // 2
        count = (mid // a + mid // b + mid // c
                 - mid // ab - mid // ac - mid // bc
                 + mid // abc)
        if count >= n:
            hi = mid
        else:
            lo = mid + 1
    return lo

The structure is identical to the two-set version. The only difference is the counting formula, which now has seven terms instead of three.

The general principle for k sets

For k sets $A_1, A_2, \ldots, A_k$, the inclusion-exclusion principle states:

$$|A_1 \cup A_2 \cup \cdots \cup A_k| = \sum_{i} |A_i| - \sum_{i < j} |A_i \cap A_j| + \sum_{i < j < l} |A_i \cap A_j \cap A_l| - \cdots + (-1)^{k+1} |A_1 \cap A_2 \cap \cdots \cap A_k|$$

You add the sizes of individual sets, subtract the sizes of all pairwise intersections, add back all triple intersections, and so on, alternating signs. The number of terms grows exponentially: there are $2^k - 1$ terms total, one for each non-empty subset of the k sets.

This means inclusion-exclusion is practical only when k is small. For $k = 2$ you have 3 terms. For $k = 3$ you have 7 terms. For $k = 10$ you already have 1023 terms, which is still feasible if computing each term is cheap. But for large k, you need different techniques.

When to use inclusion-exclusion vs brute force

Use inclusion-exclusion when:

• You need to count elements in a union of sets, and computing the size of each intersection is cheap (often $O(1)$ using LCM for divisibility problems).
• The number of sets is small (typically $k \leq 20$ or so, since you enumerate $2^k$ subsets).
• The universe is too large to iterate over directly (e.g., counting among all integers up to $10^{18}$).

Use brute force or other approaches when:

• The number of sets is large and intersection sizes are expensive to compute.
• You can iterate over the actual elements efficiently (e.g., the universe is small).
• The problem has additional structure that enables a simpler formula or sieve approach.

A common pattern is combining inclusion-exclusion with binary search on the answer, as we saw in both problems above. The binary search handles the "find the n-th element" part, and inclusion-exclusion handles the "count elements up to x" part. This combination turns problems with enormous search spaces into $O(\log(\text{range}))$ binary search iterations, each costing $O(2^k)$ for the inclusion-exclusion computation.

Complexity analysis

For the two-set case (LeetCode 878): binary search runs $O(\log(n \cdot \min(a,b)))$ iterations. Each iteration does $O(1)$ arithmetic plus a GCD computation (which is $O(\log(\min(a,b)))$ but typically precomputed once). Total: $O(\log(n \cdot \min(a,b)))$ time, $O(1)$ space.

For the three-set case (LeetCode 1201): same binary search cost, and each iteration evaluates 7 floor divisions in $O(1)$. The LCM values are precomputed. Total: $O(\log(n \cdot \min(a,b,c)))$ time, $O(1)$ space.

For the general k-set case: each binary search iteration requires $O(2^k)$ work to enumerate all subsets. Total: $O(2^k \cdot \log(\text{range}))$ time.

Compared to brute-force iteration through all integers up to the answer (which could be $O(n \cdot \min(a,b))$, easily $10^{18}$), this is astronomically faster. The combination of inclusion-exclusion for counting and binary search for finding the threshold is a powerful technique whenever you need the n-th element of a set defined by divisibility or union conditions.

Recognizing this pattern

You're probably looking at inclusion-exclusion when:

• You need to count elements satisfying at least one (or exactly $k$) of several overlapping properties, and naive union-counting double-counts intersections.
• The properties are commonly divisibility ("divisible by $a$ or $b$ or $c$"), set membership, or avoiding forbidden patterns.
• Each individual property and each intersection have a clean closed-form count, e.g., $\lfloor N/a \rfloor$ for divisibility, LCM-based for intersections of multiples.
• The universe is too large to enumerate ($N$ up to $10^9$ or $10^{18}$), but the number of properties $k$ is small (usually $k \le 20$).
• You catch yourself reasoning "$|A \cup B| = |A| + |B| - |A \cap B|$" and the answer feels like it should be a signed sum of subset-intersection sizes.

Common templates:

• Two-set divisibility union: $\lfloor N/a \rfloor + \lfloor N/b \rfloor - \lfloor N/\text{lcm}(a,b) \rfloor$, often paired with binary search. Example: Nth Magical Number.
• Three-set ugly number / divisibility union: 7-term inclusion-exclusion on $\{a, b, c\}$. Example: Ugly Number III.
• Subset enumeration over $k$ properties: iterate all $2^k$ subsets, flipping sign by parity. Example: Find the K-th Smallest Sum of a Matrix With Sorted Rows.
• Counting permutations / strings avoiding forbidden subsets: derangement-style counts via signed sums. Example: Find All Good Strings.
• Counting in $[L, R]$ with at-least-one-property: combine $f(R) - f(L-1)$ with inclusion-exclusion inside $f$. Example: Beautiful Pairs.