AdvancedMath for DSAUsed everywhere
Inclusion–exclusion: count the overlap once
|A or B| = |A| + |B| − |A and B|. Numbers ≤ 100 divisible by 2 or 3: 50 + 33 − 16 = 67.
The idea
Adding the sizes of two groups counts their overlap twice, so subtract it once. With three groups, add the singles, subtract the pairs, add the triple back.
With LCM it counts multiples fast: numbers ≤ N divisible by a or b = N/a + N/b − N/lcm(a, b). Combined with binary search on N, it finds the k-th number divisible by a or b.
Worked example
How many numbers 1..100 are divisible by 2 or 3?
- Divisible by 2: 50. By 3: 33.
- By both, i.e. by 6: 16 (counted twice above).
- 50 + 33 − 16 = 67.
In code (Python)
from math import gcd
def count_divisible(n, a, b):
lcm = a // gcd(a, b) * b
return n // a + n // b - n // lcm
def nth_magical_number(n, a, b): # n-th number divisible by a or b
lo, hi = 1, n * min(a, b)
while lo < hi:
mid = (lo + hi) // 2
if count_divisible(mid, a, b) < n:
lo = mid + 1
else:
hi = mid
return lo % (10**9 + 7)O(1) per count; O(log(n · min(a, b))) with the binary search.
How to spot it
- “divisible by a or b”, “at least one of”, counting things in overlapping groups.
Common mistakes
- Using a × b instead of lcm(a, b) for “divisible by both”.
- Forgetting to add the triple back with three sets.
Where it comes up
Go further
Up next for you · Beginner
“Have I seen this?” is a set →