core practice · coding problem
Count with inclusion-exclusion
Implement countDivisible(n, divisors) — how many integers in 1..n are divisible by AT LEAST ONE of the divisors. Use inclusion-exclusion over every non-empty subset, adding odd-sized subsets and subtracting even-sized ones, with lcm for each subset.
The mechanism
Every counting problem is a question about whether order matters and whether repetition is allowed; get those two right and the formula follows. Inclusion-exclusion exists because naive addition double-counts overlaps, and the pigeonhole principle is the one tool that proves something must exist without constructing it — which is why it shows up in hash-collision and cache arguments rather than in counting exercises.
Expected evidence
countDivisible(100,[3,5]) -> 47 (33 + 20 - 6)
Try this drill in the practice workspace →
Hints when you need them
- Iterate subsets with a bitmask; lcm(a,b) = a*b/gcd(a,b) applied across the subset.
- Sign is +1 for odd-sized subsets and -1 for even — that is what stops the overlaps being double-counted.
Watch for these mistakes
- Using a permutation where order does not matter, inflating the count by k!
- Adding the sizes of overlapping sets without subtracting the intersection
- Treating 'at least one' directly instead of counting the complement, which is usually far easier
- Assuming outcomes are equally likely when the sample space was constructed unevenly