Inclusion-Exclusion

The two-set case

To count the elements in either of two sets, add their sizes and subtract the overlap, which would otherwise be counted twice.

|A ∪ B| = |A| + |B| - |A ∩ B|

How many integers from 1 to N are divisible by 3 or 5?

long countDivisible(long n, long a, long b) {
    return n / a + n / b - n / lcm(a, b);
}

n / a counts multiples of a without a loop, and the multiples of both are exactly the multiples of their least common multiple. Using a * b instead of the LCM is correct only when a and b share no factors.

Three sets and beyond

With three sets, subtracting the pairwise overlaps removes the triple overlap too many times, so it must be added back.

|A ∪ B ∪ C| = |A| + |B| + |C|
            - |A∩B| - |A∩C| - |B∩C|
            + |A∩B∩C|

The pattern continues: add the single sets, subtract pairs, add triples, subtract quadruples. A term’s sign is positive when it involves an odd number of sets and negative when even.

Iterating over subsets

For k sets, enumerate all 2^k subsets with a bitmask and let the popcount decide the sign.

static long unionSize(long n, long[] values) {
    int k = values.length;
    long total = 0;

    for (int mask = 1; mask < (1 << k); mask++) {
        long combined = 1;
        for (int i = 0; i < k; i++) {
            if ((mask & (1 << i)) != 0) {
                combined = lcm(combined, values[i]);
                if (combined > n) break;      // nothing divides past n
            }
        }
        long count = n / combined;
        // odd number of sets -> add, even -> subtract
        total += (Integer.bitCount(mask) % 2 == 1) ? count : -count;
    }
    return total;
}

Integer.bitCount(mask) gives the number of sets in this term. Starting the loop at mask = 1 skips the empty subset, which contributes nothing.

Complementary counting

Often easier than the alternating sum: count what you do not want and subtract from the total.

How many integers from 1 to N are coprime to M?

Counting them directly is awkward. Counting those sharing a factor with M is inclusion-exclusion over M’s distinct prime factors — and the complement gives the answer.

static long countCoprime(long n, long m) {
    List<Long> primes = distinctPrimeFactors(m);
    int k = primes.size();
    long total = 0;

    for (int mask = 0; mask < (1 << k); mask++) {
        long product = 1;
        for (int i = 0; i < k; i++) {
            if ((mask & (1 << i)) != 0) product *= primes.get(i);
        }
        long count = n / product;
        total += (Integer.bitCount(mask) % 2 == 0) ? count : -count;
    }
    return total;
}

Note this version starts at mask = 0 and uses the opposite sign convention, because the empty subset contributes the full count n from which the rest is subtracted. Which convention you need depends on whether you are counting the union or its complement — derive it on a tiny case rather than recalling it.

Only distinct prime factors matter. Including a repeated prime would double-count. See Number Theory Basics.

Two dimensions

The 2D prefix-sum query is inclusion-exclusion on rectangles:

long sum = pre[r2 + 1][c2 + 1]
         - pre[r1][c2 + 1]
         - pre[r2 + 1][c1]
         + pre[r1][c1];

Two overlapping strips are removed, and their shared corner — subtracted twice — is added back. The same reasoning gives the area of a union of rectangles, and the sign pattern is identical.

Derangements

How many permutations leave no element in its original position?

Let A_i be the permutations fixing position i. You want the complement of the union of all A_i. Inclusion-exclusion collapses to a clean recurrence:

static long[] derangements(int n, long mod) {
    long[] d = new long[n + 1];
    d[0] = 1;
    if (n >= 1) d[1] = 0;
    for (int i = 2; i <= n; i++) {
        d[i] = (i - 1) * (d[i - 1] + d[i - 2]) % mod;
    }
    return d;
}

This is worth knowing as a finished result. The alternating-sum derivation is instructive, but the recurrence is what you would actually write, and it is O(N) rather than O(N) terms of factorials and inverses.

When inclusion-exclusion applies

Related