044 — Inclusion-Exclusion Basic¶
এবার একটা চিন্তার অস্ত্র যেটা ছাড়া "অন্তত একটা" গোছের প্রশ্ন প্রায় অসম্ভব। মূল ভয়টা: দুটো দলে যোগ করতে গিয়ে যারা দুই দলেই আছে, তাদের দুবার গুনে ফেলা। সমাধান একদম সহজ — যা দুবার গুনলে, একবার বিয়োগ করে দাও। এই যোগ-বিয়োগের পালা-নাচই inclusion-exclusion। Venn diagram-টা মাথায় গেঁথে নাও, তাহলে formula নিজেই বেরিয়ে আসবে।
Source¶
- Original source: CP-Algorithms (inclusion-exclusion)
- Platform: CP-Algorithms — https://cp-algorithms.com/combinatorics/inclusion-exclusion.html
- Topic: Math-based programming fundamentals → Level 3: Counting & Combinatorics
- Difficulty: Medium
- Pattern: overcount correction (inclusion-exclusion)
- Basic idea inherited from: 041 — Combination Basic (set-গোনা আর overcount শোধরানোর ভাবনা)
1. Problem in simple words¶
কয়েকটা দল (set) আছে। জানতে চাই অন্তত একটা দলে কতগুলো জিনিস আছে — মানে দলগুলোর union-এর আকার।
ভুল উত্তর: সব দলের আকার যোগ করা। কারণ যেসব জিনিস একাধিক দলে আছে, তারা বারবার গোনা হয়ে যায়।
সবচেয়ে সহজ রূপ (দুই দল): |A ∪ B| বের করা — A বা B (বা দুটোতেই) আছে এমন জিনিস কয়টা।
ক্লাসিক CP রূপ: 1 থেকে N-এ কয়টা সংখ্যা a বা b দিয়ে ভাগ যায়?
2. What is the math idea?¶
মূল idea — যা বেশিবার গুনলে, সেটা বিয়োগ করে শোধরাও।
দুই দলে:
|A| + |B|-এ দুই দলেই থাকা জিনিসগুলো (intersection) দুবার গোনা হয়, তাই একবার বিয়োগ।
তিন দলে ঢেউটা আরেক ধাপ গড়ায়:
নিয়ম (মন্ত্র): বিজোড় সংখ্যক দলের intersection যোগ, জোড় সংখ্যকের বিয়োগ — পালা করে।
3. Which basic idea does this inherit from?¶
এটা 041 (Combination Basic)-এর চিন্তা-ধারার আত্মীয়: সেখানে nCr-এ একই দল r! বার গোনা হয়েছিল, তাই r! দিয়ে ভাগ করে overcount শোধরেছিলাম। এখানেও মূল সুর সেই — গোনার সময় কিছু জিনিস বেশিবার গোনা পড়ে, সেটা যোগ-বিয়োগ করে শোধরানো।
পার্থক্য: 041-এ একই গুণিতকে overcount (তাই ভাগ), এখানে overlapping set-এ overcount (তাই বিয়োগ-যোগ)। আর কোন intersection কতবার গোনা হলো সেটা বুঝতে combination-এর C(set, j) চিন্তাও লুকিয়ে আছে — তাই 041 ভিত্তি।
4. Real-life analogy¶
ভাবো তোমার ক্লাসে দুটো ক্লাব — cricket আর football। শিক্ষক জানতে চান অন্তত একটা ক্লাবে কতজন আছে।
cricket-এ 25, football-এ 18। সরাসরি যোগ করলে 43। কিন্তু যারা দুটো ক্লাবেই নাম লিখিয়েছে (ধরো 10 জন), তাদের তো একবার cricket-এ, একবার football-এ — দুবার গুনে ফেললে!
তাই সেই 10 জনকে একবার বিয়োগ করো: 25 + 18 − 10 = 33। এই "দুই জায়গায় থাকা মানুষকে একবার বাদ" — এটাই inclusion-exclusion-এর হৃদয়।
5. Visual explanation¶
প্রথমে দেখো Venn diagram-এ কেন বিয়োগ লাগে (cricket 25, football 18, দুটোই 10):
cricket (25) football (18)
+-------------+---------+-------------+
| | | |
| 15 | 10 | 8 |
| (শুধু crick) | (দুটোই) | (শুধু foot) |
| | | |
+-------------+---------+-------------+
মাঝের 10 দুই বৃত্তেই -> |A|+|B|-এ দুবার গোনা
তাই একবার বিয়োগ: 25 + 18 − 10 = 33
আলাদা করে: 15 + 10 + 8 = 33 ✓
এবার দেখো তিন দলে কীভাবে যোগ-বিয়োগ পালা করে:
|A∪B∪C| = +|A| +|B| +|C| (একক -> যোগ)
−|A∩B| −|B∩C| −|A∩C| (জোড়া -> বিয়োগ)
+|A∩B∩C| (তিন -> যোগ)
মাঝের (তিনটাতেই থাকা) জিনিস: যোগে 3 বার, জোড়ায় 3 বার বিয়োগ
-> এখন 0 বার! তাই শেষে একবার ফেরত যোগ
লক্ষ করো — প্রতিটা জিনিস ঠিক একবার গোনা হওয়ার জন্যই এই পালা-নাচ।
6. Example input and output¶
দুই দল union:
|A|=25, |B|=18, |A∩B|=10 -> 33
1..N-এ a বা b দিয়ে ভাগ যায় (count_divisible):
N=100, a=2, b=3 -> 67 (50 + 33 − 16)
N=100, a=2, b=5 -> 60 (50 + 20 − 10)
N=15, a=3, b=5 -> 7 (5 + 3 − 1)
তিন দল union:
|A|=|B|=|C|=10, সব জোড়া=3, মাঝ=1 -> 10·3 − 3·3 + 1 = 22
Edge case: দুই দলে কোনো overlap না থাকলে (|A∩B| = 0) union = |A| + |B| — বিয়োগ কিছু নেই। আর সব দল এক হলে union = একটা দলের আকার।
7. Brute force thinking¶
সবচেয়ে সরাসরি — সব জিনিস একে একে দেখে set-এ ফেলে গোনা। যেমন 1..N-এ a বা b দিয়ে ভাগ যায় কয়টা:
def count_divisible_brute(N, a, b):
count = 0
for x in range(1, N + 1):
if x % a == 0 or x % b == 0:
count += 1
return count
প্রতিটা সংখ্যা ঘুরে দেখি ভাগ যায় কিনা — একদম ঠিক উত্তর, আর formula verify করার নিখুঁত উপায়। সাধারণ union-এর জন্য Python-এর set দিয়ে union করেও সরাসরি গোনা যায়।
8. Why brute force may be slow¶
সমস্যা হলো এই loop N বার চলে। N ছোট হলে ঠিক আছে, কিন্তু:
N = 10^9, a = 2, b = 3 হলে:
brute force: 100 কোটি বার loop -> Time Limit Exceeded
inclusion-exclusion: N//2 + N//3 − N//6 -> মাত্র 3 টা ভাগ, O(1)!
বড় range-এ একে একে গোনা অসম্ভব ধীর, অথচ formula এক নিমেষে উত্তর দেয়। আর set দিয়ে union করলে memory-ও O(N) — বিশাল N-এ অচল।
9. Better thinking¶
মূল insight: একে একে না গুনে প্রতিটা set কত বড় সেটা সরাসরি হিসাব করো, তারপর overlap বিয়োগ করো।
1..N-এ a-এর গুণিতক ঠিক N // a টা — গোনা লাগে না! তাই:
def count_divisible(N, a, b):
from math import gcd
lcm = a * b // gcd(a, b) # a আর b দুটোতেই ভাগ = lcm-এর গুণিতক
return N // a + N // b - N // lcm
N // lcm কেন? "a এবং b দুটোতেই ভাগ যায়" মানে lcm(a, b)-এর গুণিতক (Level 1-এর gcd/lcm এখানে ফিরল!)। তিন বা বেশি set-এ একই নিয়ম bitmask দিয়ে সাধারণ করা যায় (section 12)।
10. Thinking tweak¶
আসল "আহা" মুহূর্ত: আগে সব যোগ করে নাও যেন overlap নেই — তারপর যতবার বেশি গুনলে, ততবার বিয়োগ-যোগ করে শোধরাও।
একটা জিনিস যদি ঠিক j টা set-এ থাকে, naive যোগে সে j বার গোনা হয়; inclusion-exclusion-এর পালা-নাচ (যোগ − জোড়া + ত্রয়ী − ...) ঠিক এমনভাবে সাজানো যে শেষে সে ঠিক একবার গোনা হয়। এই "overcount-কে পালা করে শোধরাও" চিন্তাটাই অস্ত্র — আর "এবং" মানে intersection (সংখ্যায় lcm) — এই দুই গেঁথে নাও।
11. Step-by-step dry run¶
চলো N = 100, a = 2, b = 3 চালাই:
| ধাপ | হিসাব | মান |
|---|---|---|
| 2-এর গুণিতক | 100 // 2 | 50 |
| 3-এর গুণিতক | 100 // 3 | 33 |
| lcm(2,3) = 6 | — | 6 |
| 6-এর গুণিতক (দুটোই) | 100 // 6 | 16 |
| union | 50 + 33 − 16 | 67 |
মানে 1..100-এ 67টা সংখ্যা 2 বা 3 দিয়ে ভাগ যায়।
হাতে যাচাই (ছোট, N=15, a=3, b=5): 3-এর গুণিতক {3,6,9,12,15} = 5টা, 5-এর {5,10,15} = 3টা, 15-এর {15} = 1টা → 5+3−1 = 7। তালিকা: {3,5,6,9,10,12,15} — ঠিক 7টা ✓।
12. Python solution¶
from math import gcd
def union_two(a_size, b_size, inter_size):
"""|A ∪ B| = |A| + |B| − |A ∩ B|।"""
return a_size + b_size - inter_size
def count_divisible(N, a, b):
"""1..N-এ a বা b দিয়ে ভাগ যায় এমন সংখ্যা কয়টা।"""
lcm = a * b // gcd(a, b)
return N // a + N // b - N // lcm
def count_divisible_any(N, divisors):
"""1..N-এ divisors-এর যেকোনোটি দিয়ে ভাগ যায় কয়টা (general inclusion-exclusion)।
প্রতিটা অ-খালি উপসেট ঘুরি: বিজোড় সংখ্যক হলে যোগ, জোড় হলে বিয়োগ;
সেই উপসেটের সব divisor-এর lcm-এর গুণিতক = N // lcm।
"""
from math import lcm as _lcm
m = len(divisors)
total = 0
for mask in range(1, 1 << m): # 1 থেকে 2^m − 1
cur_lcm = 1
bits = 0
for i in range(m):
if mask & (1 << i):
cur_lcm = _lcm(cur_lcm, divisors[i])
bits += 1
cnt = N // cur_lcm
if bits % 2 == 1: # বিজোড় -> যোগ
total += cnt
else: # জোড় -> বিয়োগ
total -= cnt
return total
# --- brute force verifier ---
def count_divisible_brute(N, divisors):
count = 0
for x in range(1, N + 1):
if any(x % d == 0 for d in divisors):
count += 1
return count
# --- ছোট test গুলো (সব pass করা উচিত) ---
assert union_two(25, 18, 10) == 33
assert union_two(10, 5, 0) == 15 # overlap নেই
assert count_divisible(100, 2, 3) == 67
assert count_divisible(100, 2, 5) == 60
assert count_divisible(15, 3, 5) == 7
# দুই-divisor formula == general == brute (ছোট range জুড়ে)
for N in range(0, 60):
for a in range(2, 7):
for b in range(2, 7):
f = count_divisible(N, a, b)
g = count_divisible_any(N, [a, b])
br = count_divisible_brute(N, [a, b])
assert f == g == br
# তিন-divisor general == brute
for N in range(0, 40):
assert count_divisible_any(N, [2, 3, 5]) == count_divisible_brute(N, [2, 3, 5])
print(union_two(25, 18, 10)) # 33
print(count_divisible(100, 2, 3)) # 67
print(count_divisible_any(100, [2, 3, 5])) # 74
print("সব test pass!")
13. Line-by-line explanation¶
দুই দলের মূল formula — যোগ করে, দুবার গোনা intersection একবার বিয়োগ।
1..N-এ a-এর গুণিতক N//a, b-এর N//b, "দুটোই" মানে lcm(a,b)-এর গুণিতক N//lcm — সেটাই বিয়োগ।
for mask in range(1, 1 << m):
... cur_lcm = lcm(...) ...
if bits % 2 == 1: total += cnt
else: total -= cnt
general version — প্রতিটা অ-খালি উপসেট (bitmask) ঘুরি, সেই divisor-গুলোর lcm-এর গুণিতক গুনি; উপসেটে দল-সংখ্যা বিজোড় হলে যোগ, জোড় হলে বিয়োগ — এটাই পালা-নাচ।
বাকি assert লাইনগুলো formula, general আর brute force — তিন পথ মিলিয়ে যাচাই করছে। সব মিললে শেষে সব test pass!।
14. Output walkthrough¶
চালালে যা ছাপবে:
প্রথম: union_two(25,18,10) = 33। দ্বিতীয়: count_divisible(100,2,3) = 67। তৃতীয়: 1..100-এ 2/3/5 দিয়ে ভাগ যায় = 74 (50+33+20 − 16−10−6 + 1)। আগের সব assert (formula বনাম general বনাম brute) চুপচাপ pass করেছে। শেষে সব test pass!।
15. Time complexity¶
দুই/তিন নির্দিষ্ট set-এর formula O(1) (গুটিকয় ভাগ)। general version-এ m টা set হলে 2^m টা উপসেট × প্রতিটায় O(m) lcm = O(2ᵐ · m) — m ছোট (যেমন ≤ 20) থাকলে দ্রুত। brute force-এর O(N)-এর তুলনায় বিশাল N-এ আকাশ-পাতাল উন্নতি।
16. Space complexity¶
O(1) — শুধু গুটিকয় variable (mask, lcm, total); কোনো বড় set বা list রাখা হয় না।
17. Common mistakes¶
- Intersection বিয়োগ ভুলে যাওয়া —
|A|+|B|লিখে থেমে যাওয়া; − |A∩B|-ই পদ্ধতির প্রাণ। - তিন set-এ মাঝেরটা ফেরত যোগ না করা — তিন-intersection শেষে + দিয়ে ফিরবে, নাহলে সে 0 বার গোনা থাকবে।
- "এবং" মানে lcm না বোঝা — "a আর b দুটোতেই ভাগ" = lcm(a,b)-এর গুণিতক,
a×b-এর নয় (যদি a,b coprime না হয়)। - খালি উপসেট গোনা — general-এ mask 0 (কোনো set না) বাদ দিতে হবে; তাই
range(1, ...)। - যোগ/বিয়োগ চিহ্ন উল্টানো — বিজোড় দল = যোগ, জোড় দল = বিয়োগ; এক ধাপ ভুল হলেই উত্তর নষ্ট।
18. Harder problems that inherit this idea¶
- CP-Algorithms — Inclusion-Exclusion (https://cp-algorithms.com/combinatorics/inclusion-exclusion.html) — derangement, coprime counting সহ অনেক প্রয়োগ।
- 050 — Derangement Intro (এই repo) — derangement-এর একটা রূপ inclusion-exclusion দিয়েই বেরোয়।
- Project Euler / CSES counting problems — "অন্তত একটা শর্ত মানে কয়টা" — প্রায়ই inclusion-exclusion।
19. Pattern learned¶
Inclusion-exclusion (add singles − pairs + triples − …) — union গুনতে আগে সব যোগ, তারপর overlap পালা করে বিয়োগ-যোগ; "এবং" = intersection (সংখ্যায় lcm)। মূল signal: "অন্তত একটা / যেকোনোটা দিয়ে ভাগ / union" দেখলেই inclusion-exclusion।
20. Final summary¶
ভবিষ্যতের আমাকে এক লাইনে: "|A∪B| = |A|+|B|−|A∩B|; বিজোড় দল যোগ, জোড় দল বিয়োগ। 'অন্তত একটা'/'a বা b দিয়ে ভাগ' দেখলেই এটা, আর 'এবং' মানে lcm।"
পরের ধাপ → 045 — Count Pairs (C(n,2)-এর সরাসরি প্রয়োগ — কয়টা জোড়া)।
ফিরে দেখা: আগের ধাপ → 041 — Combination Basic · এই level-এর map → ../README.md · concept ঝালাই → ../concept-notes.md · template → ../../../templates/math-problem-note-template.md।
মনে রাখার নিয়ম (legal): সব নিজের ভাষায় লেখা; problem statement copy করা হয়নি; official link শুধু attribution-এর জন্য; "asked by Google/Amazon" এমন দাবি নয় — বরং "common interview pattern" / "Google-style pattern"।