Inclusion-Exclusion Principle

This is an extension topic beyond most interviews; it pays off in harder OAs that count objects satisfying "at least one of" or "none of" several conditions, where direct counting would double count.

Intuition

For two sets, |A or B| = |A| + |B| - |A and B|: adding both counts the overlap twice, so subtract it once. For three sets you add the singles, subtract the pairs, and add back the triple. In general, for conditions P1..Pk:

|at least one|  =  sum over non-empty S of (-1)^(|S|+1) * N(S)
|none|          =  sum over all S        of (-1)^|S|     * N(S)

where N(S) is the number of objects satisfying every condition in S (and N(empty) = total). The point is that "all of these" intersections are usually easy to count even when "at least one" is not: integers divisible by all of a, b are just the multiples of lcm(a, b).

With k conditions there are 2^k subsets, so the method is practical for k up to about 20, and a bitmask loop enumerates the subsets naturally.

When to use it in interviews / OAs

• "How many numbers up to n are divisible by a, b or c?" and the binary-searched variant "find the n-th such number".
• Counting with upper bounds: distributions where each part is at most c_i.
• "No element in its original position" (derangements), "every color/box used at least once" (surjections).
• Counting coprime numbers or pairs: exclude multiples of each prime factor.

Divisibility by any of several numbers

from math import comb, factorial, gcd


def count_divisible_by_any(n: int, divisors: list[int]) -> int:
    # how many x in [1, n] are divisible by at least one of the divisors
    divisors = list(set(divisors))
    k = len(divisors)
    total = 0
    for mask in range(1, 1 << k):
        l = 1
        for i in range(k):
            if mask >> i & 1:
                l = l * divisors[i] // gcd(l, divisors[i])
                if l > n:  # no multiples in range; also stops the lcm from exploding
                    break
        total += n // l if mask.bit_count() % 2 else -(n // l)
    return total


def nth_divisible(n: int, a: int, b: int, c: int) -> int:
    # the n-th positive integer divisible by a, b or c: binary search on the answer
    lo, hi = 1, n * min(a, b, c)
    while lo < hi:
        mid = (lo + hi) // 2
        if count_divisible_by_any(mid, [a, b, c]) >= n:
            hi = mid
        else:
            lo = mid + 1
    return lo

Intersections use the lcm, not the product: multiples of both 4 and 6 are multiples of 12, not 24.

Distributions with upper bounds

How many solutions does x1 + ... + xk = n have with 0 <= xi <= c_i? Without caps, stars and bars gives C(n + k - 1, k - 1). Let condition Pi be "xi exceeds its cap". Forcing the parts in S to break their caps means giving each of them c_i + 1 up front, after which the rest is unconstrained. Then the answer is the "none of the conditions" sum:

def bounded_compositions(n: int, caps: list[int]) -> int:
    # solutions of x1 + ... + xk = n with 0 <= xi <= caps[i], k >= 1
    k = len(caps)
    total = 0
    for mask in range(1 << k):
        # every i in mask breaks its cap: hand it caps[i] + 1 up front
        rest = n - sum(caps[i] + 1 for i in range(k) if mask >> i & 1)
        if rest < 0:
            continue
        ways = comb(rest + k - 1, k - 1)
        total += -ways if mask.bit_count() % 2 else ways
    return total

Derangements and surjections

A derangement is a permutation with no fixed point. Let Pi be "position i is fixed". Fixing a set of j positions leaves (n - j)! permutations, so D(n) = sum of (-1)^j * C(n, j) * (n - j)!. The same numbers satisfy a simple recurrence. Put element n at some position i (n - 1 choices). Either element i takes position n, and the remaining n - 2 elements form a derangement, or it does not, and treating position n as element i's forbidden spot leaves a derangement of n - 1 elements: D(n) = (n - 1) * (D(n - 1) + D(n - 2)).

def derangements(n: int) -> int:
    # D(0) = 1, D(1) = 0, D(n) = (n - 1) * (D(n - 1) + D(n - 2))
    if n == 0:
        return 1
    a, b = 1, 0  # D(i - 2), D(i - 1)
    for i in range(2, n + 1):
        a, b = b, (i - 1) * (a + b)
    return b


def derangements_ie(n: int) -> int:
    # inclusion-exclusion over the set of fixed points
    return sum((-1) ** j * comb(n, j) * factorial(n - j) for j in range(n + 1))


def surjections(n: int, k: int) -> int:
    # maps from n labeled items onto k labeled boxes with no box left empty
    return sum((-1) ** j * comb(k, j) * (k - j) ** n for j in range(k + 1))

For surjections, the condition Pj is "box j stays empty"; avoiding a chosen set of j boxes leaves (k - j)^n maps. D(n) / n! tends to 1/e, a fun fact behind "probability that nobody gets their own hat back".

Complexity

2^k subsets, O(k) work per term (building one lcm or one binomial). Derangements by recurrence are O(n); surjections are O(k log n) with fast (binary) exponentiation. For k beyond about 20 conditions, look for structure (symmetry, as in derangements, groups the 2^k terms into k + 1 classes of identical terms).

Common pitfalls

• Sign errors: odd-sized subsets are added for "at least one" and subtracted for "none". Check with k = 1 and k = 2 by hand.
• Product instead of lcm when the numbers share factors, and duplicates in the input (deduplicate first).
• lcm overflow in fixed-width languages: stop as soon as the lcm exceeds n, since its contribution is 0.
• Negative remainders in bounded distributions: skip terms where the forced amounts exceed n, and do not call a binomial with a negative top.
• Exponential blow-up: 2^k with k = 30 is a billion terms. Group symmetric conditions or switch to DP.

Interview variations

• Ugly number III (n-th number divisible by a, b or c) and n-th magical number (two numbers): inclusion-exclusion inside a binary search.
• Count integers in a range coprime to m: exclude multiples of each distinct prime factor of m.
• Count distributions with per-box limits: bounded stars and bars.
• Find the derangement of an array (count modulo 10^9 + 7): the recurrence with modular arithmetic.
• Ways to paint or assign so that every option is used: surjections, often combined with permutations of the options.
• Pairs or subsequences with gcd exactly g: count those with gcd a multiple of g, then subtract the counts for 2g, 3g, ... processing g from large to small.