Problem link ও উৎস
- Original source: Classic beginner exercise
- Platform: Classic exercise
- Topic: Math-based programming fundamentals → Level 1: Divisibility, Prime, GCD, LCM
- Difficulty: Easy
- Pattern: divisibility
- Basic idea inherited from: 001 (Even or Odd)
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
দুটো integer `a` আর `b` দেওয়া আছে। বলতে হবে — `a` কি `b` দিয়ে **নিঃশেষে ভাগ যায়**? মানে ভাগ করলে কোনো কিছু বাকি থাকে না তো?
যেমন `12` কি `4` দিয়ে ভাগ যায়? হ্যাঁ — `12 = 4 × 3`, বাকি 0। `12` কি `5` দিয়ে? না — `12 = 5 × 2 + 2`, বাকি 2।
পাশাপাশি, একটা সংখ্যা ছোট ছোট সংখ্যা (2, 3, 5, 9, 10...) দিয়ে ভাগ যায় কিনা — সেটা চটজলদি বলার কিছু **rule**-ও শিখব।
### Input ও output {#6-example-input-and-output}
```text
divides(a, b) — a কি b দিয়ে ভাগ যায়?
------------------------------------
divides(12, 4) -> True (12 = 4×3)
divides(12, 5) -> False (বাকি 2)
divides(100, 10)-> True
divides(7, 1) -> True (সবাই 1 দিয়ে ভাগ যায়)
divides(0, 5) -> True (0 = 5×0, বাকি 0 — 0 সবার গুণিতক)
rule চেক:
is_div_by_3(123) -> True (digit sum 6)
is_div_by_9(123) -> False (digit sum 6, 9 দিয়ে যায় না)
is_div_by_5(45) -> True (last digit 5)
```
দুটো edge case: **b = 1-এ সবসময় True** (সব সংখ্যা 1 দিয়ে ভাগ যায়), আর **a = 0-এ True** (0 যেকোনো কিছুর গুণিতক)। সাবধান — `b = 0` দিয়ে ভাগ অসংজ্ঞায়িত (নিচে common mistake)।
### চেনা উদাহরণে বোঝা {#4-real-life-analogy}
ভাবো তোমার কাছে `a`টা চকলেট, আর তুমি `b` জন বন্ধুর মধ্যে **সমানভাবে** ভাগ করতে চাও।
- সবাই সমান পেল, হাতে একটাও রইল না → `a % b == 0` → ভাগ যায় (ঝগড়াহীন ভাগ)
- সমান ভাগের পরেও কিছু চকলেট হাতে রয়ে গেল → সেই বাকি অংশই remainder → ভাগ যায় না
যেমন 12টা চকলেট 4 জনকে দিলে প্রত্যেকে 3টা, হাতে শূন্য — শান্তি। কিন্তু 5 জনকে দিলে প্রত্যেকে 2টা, হাতে 2টা বাকি — সেই 2টা নিয়ে টানাটানি। **Divisibility মানে হাতে কিছু না থাকা ভাগ।**
আর rule-গুলো? সেগুলো হলো শর্টকাট — পুরো ভাগ না করেই আগেভাগে আঁচ করা "এই ভাগটা মসৃণ হবে কিনা"।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#3-which-basic-idea-does-this-inherit-from}
সরাসরি **001 (Even or Odd)** থেকে।
001-এ আমরা `n % 2 == 0` দিয়ে even/odd বলতাম — সেটা আসলে **"2 দিয়ে ভাগ যায় কিনা"** ছাড়া আর কিছু নয়! মানে even/odd হলো divisibility-র সবচেয়ে ছোট, সবচেয়ে চেনা ঘটনা।
```
001: n % 2 == 0 -> 2 দিয়ে ভাগ যায় কিনা (even)
011: a % b == 0 -> যেকোনো b দিয়ে ভাগ যায় কিনা (general)
```
011 হলো 001-এরই সাধারণীকরণ (generalization): 2-এর জায়গায় যেকোনো `b`। আর 001-এ শেখা "last digit-ই বলে দেয় even/odd" — সেটাই এখানে rule of 2 আর rule of 5 হয়ে ফিরছে। তাই 001 না বুঝলে এই rule-গুলোও আবছা থাকবে।
### ভেতরের অঙ্ক {#2-what-is-the-math-idea}
মূল idea — **divisibility = remainder 0**। `b` যদি `a`-কে ভাগ করে, তবে `a % b == 0`। এটুকুই মূল সংজ্ঞা।
কিন্তু মজাটা এখানে — কিছু বিশেষ `b`-এর জন্য পুরো ভাগ না করেও বলে দেওয়া যায়, শুধু digit দেখে। এগুলোই **divisibility rules**:
```
2 -> last digit even (0,2,4,6,8)
3 -> সব digit-এর যোগফল 3 দিয়ে ভাগ যায়
5 -> last digit 0 বা 5
9 -> সব digit-এর যোগফল 9 দিয়ে ভাগ যায়
10 -> last digit 0
4 -> শেষ দুই digit মিলে যে সংখ্যা, সেটা 4 দিয়ে ভাগ যায়
```
এই rule-গুলোর পেছনে modular arithmetic-এর সূত্র আছে (Level 2-তে পুরো প্রমাণ দেখব), কিন্তু এখন ব্যবহারটাই শিখি।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#7-brute-force-thinking}
মূল divisibility চেক তো সরল — `a % b == 0`। কিন্তু ধরো `%` operator নেই, বা rule-গুলো হাতে যাচাই করতে চাও। তখন "হাতে গুনে" করার ভাবনা — `b` বারবার যোগ করে দেখো ঠিক `a`-তে পৌঁছায় কিনা:
```python
def divides_brute(a, b):
if b == 0:
return False
total = 0
while total < a:
total += b # b, 2b, 3b, ... জমাও
return total == a # ঠিক a-তে থামল?
```
আর rule যাচাইয়ের brute version — rule ব্যবহার না করে সরাসরি `% 3` দিয়ে মিলিয়ে দেখা যে rule সত্যিই ঠিক উত্তর দেয় কিনা। এই "সরল দিয়ে চালাক যাচাই" অভ্যাসটা এই level-এ বারবার লাগবে।
### কোথায় বেশি কাজ হতে পারে {#8-why-brute-force-may-be-slow}
`b` বারবার যোগ করার version ভয়াবহ ধীর হতে পারে:
- loop ঘোরে `a / b` বার। `a` বিশাল (যেমন 10⁹) আর `b` ছোট (যেমন 2) হলে — প্রায় 50 কোটি বার যোগ। অথচ `a % b` এক ধাপে উত্তর দিত।
```text
a = 1000000000, b = 2 হলে:
brute (যোগ করে) : ~500000000 বার loop (O(a/b), ভয়ংকর ধীর)
smart (% দিয়ে) : ঠিক 1 বার % (O(1), চোখের নিমেষে)
```
আর rule-গুলোর মাহাত্ম্য এখানেই: rule of 3-এ পুরো বড় সংখ্যা ভাগ না করে শুধু digit যোগ করি — যা digit সংখ্যার সমান (`O(log a)`) কাজ, পুরো ভাগের চেয়ে অনেক হালকা মানসিক হিসাব (বিশেষত হাতে-কলমে)।
মূল শিক্ষা: যেটা এক ধাপের (`%`), তার জন্য loop চালানো অপচয়।
### আরও ভালোভাবে ভাবা {#9-better-thinking}
মূল চেক সরাসরি `%` দিয়ে — এক ধাপ:
```python
def divides(a, b):
if b == 0:
return False # 0 দিয়ে ভাগ অসংজ্ঞায়িত
return a % b == 0
```
আর rule-গুলো digit ব্যবহার করে (Level 0-এর digit-extraction এখানে কাজে লাগে):
```python
def digit_sum(n):
n = abs(n)
s = 0
while n > 0:
s += n % 10
n //= 10
return s
def is_div_by_3(n):
return digit_sum(n) % 3 == 0 # digit sum 3 দিয়ে গেলে n-ও যায়
def is_div_by_9(n):
return digit_sum(n) % 9 == 0
```
লক্ষ করো — rule of 3/9-এ আমরা Level 0-এর `digit_sum` (002) সরাসরি পুনর্ব্যবহার করছি। পুরোনো হাতিয়ার নতুন কাজে।
### ভাবনার পরিবর্তন {#10-thinking-tweak}
মূল মোচড় দুই স্তরে:
- **সাধারণ চেক:** "ভাগ যায় কিনা" = "remainder শূন্য কিনা" = `a % b == 0`। আলাদা করে ভাগফল বের করার দরকার নেই, শুধু **বাকিটা** দেখো।
- **rule-এর জাদু:** কিছু সংখ্যার জন্য (3, 9) **digit sum-এর remainder = মূল সংখ্যার remainder**। তাই বড় সংখ্যা না ঘেঁটে digit যোগ করেই উত্তর। কেন? কারণ `10 ≡ 1 (mod 9)` — 10-এর যেকোনো power 9 দিয়ে ভাগে 1 বাকি রাখে, তাই প্রতিটা digit তার place value নির্বিশেষে নিজের মান-ই অবদান রাখে। (পুরো প্রমাণ Level 2-তে; এখন এটুকু "আহা" যথেষ্ট।)
এই "remainder-ই আসল, ভাগফল নয়" আর "digit sum মূল সংখ্যার mod 9/3 ধরে রাখে" — দুই tweak মাথায় গাঁথো।
### ছবিতে বোঝা {#5-visual-explanation}
`a % b` কে "বারবার b সরিয়ে শেষে কী বাকি" ভাবো — `12 ÷ 4` আর `12 ÷ 5` পাশাপাশি:
```text
12 ÷ 4 : [4][4][4] -> 3 গুচ্ছ, হাতে 0 বাকি -> 12 % 4 = 0 -> ভাগ যায় ✓
\_/\_/\_/
12 ÷ 5 : [5][5] .. -> 2 গুচ্ছ, হাতে [2] বাকি -> 12 % 5 = 2 -> ভাগ যায় না ✗
\_/\_/ ^^
বাকি 2
```
আর rule of 3-টা চোখে দেখো (`123` কি 3 দিয়ে ভাগ যায়?):
```text
123 -> digit sum = 1 + 2 + 3 = 6 -> 6 % 3 = 0 -> হ্যাঁ, 123 ভাগ যায় (123 = 3×41)
124 -> digit sum = 1 + 2 + 4 = 7 -> 7 % 3 = 1 -> না, 124 ভাগ যায় না
```
পুরো সংখ্যা ভাগ না করেই, শুধু digit যোগ করে উত্তর — এটাই rule-এর সৌন্দর্য।
### ছোট input-এ ধাপে ধাপে {#11-step-by-step-dry-run}
প্রথমে `divides(12, 4)` — smart version এক ধাপ:
```text
b = 4 ≠ 0, তাই এগোই
12 % 4 -> 12 = 4×3 + 0 -> remainder 0 -> 0 == 0 -> True
```
এবার rule of 3 দিয়ে `is_div_by_3(123)` — digit sum loop হাতে চালাই:
| step | n (শুরুতে) | n % 10 | s (পরে) | n //= 10 |
| --- | --- | --- | --- | --- |
| 1 | 123 | 3 | 0 + 3 = 3 | 12 |
| 2 | 12 | 2 | 3 + 2 = 5 | 1 |
| 3 | 1 | 1 | 5 + 1 = 6 | 0 |
digit sum = 6, তারপর `6 % 3 == 0` → **True**। মিলিয়ে দেখো: `123 = 3 × 41`, সত্যিই 3 দিয়ে ভাগ যায়। দুই পথ (সরাসরি `123 % 3` আর rule) একই উত্তর দেয় — এটাই rule-এর নির্ভরযোগ্যতার প্রমাণ।
## কোড ও ব্যাখ্যা {#code}
### Python {#12-python-solution}
```python
def divides(a, b):
"""a কি b দিয়ে নিঃশেষে ভাগ যায়? (b = 0 হলে False)"""
if b == 0:
return False
return a % b == 0
def digit_sum(n):
"""Level 0 (002)-এর digit sum — rule-এ লাগবে।"""
n = abs(n)
s = 0
while n > 0:
s += n % 10
n //= 10
return s
def is_div_by_2(n):
return n % 2 == 0 # last bit / last digit even
def is_div_by_3(n):
return digit_sum(n) % 3 == 0 # digit sum 3 দিয়ে যায়
def is_div_by_5(n):
return n % 10 in (0, 5) # last digit 0 বা 5
def is_div_by_9(n):
return digit_sum(n) % 9 == 0 # digit sum 9 দিয়ে যায়
# --- ছোট test গুলো (সব pass করা উচিত) ---
assert divides(12, 4) is True
assert divides(12, 5) is False
assert divides(100, 10) is True
assert divides(7, 1) is True # সবাই 1 দিয়ে ভাগ যায়
assert divides(0, 5) is True # 0 সবার গুণিতক
assert divides(5, 0) is False # 0 দিয়ে ভাগ অসংজ্ঞায়িত
# rule গুলো সরাসরি % দিয়ে মিলিয়ে যাচাই (সরল দিয়ে চালাক)
for n in [0, 3, 9, 18, 45, 100, 123, 124, 999, 1000]:
assert is_div_by_2(n) == (n % 2 == 0)
assert is_div_by_3(n) == (n % 3 == 0)
assert is_div_by_5(n) == (n % 5 == 0)
assert is_div_by_9(n) == (n % 9 == 0)
assert is_div_by_3(123) is True # digit sum 6
assert is_div_by_9(123) is False # digit sum 6, 9-এ যায় না
assert is_div_by_9(999) is True # digit sum 27
print(divides(12, 4)) # True
print(is_div_by_3(123)) # True
print(is_div_by_5(45)) # True
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#13-line-by-line-explanation}
```
def divides(a, b):
if b == 0:
return False
return a % b == 0
```
মূল চেক। আগে `b == 0` আটকাই — কারণ শূন্য দিয়ে ভাগ Python-এ error (`ZeroDivisionError`) দেয়, তাই আগেই `False` ফেরাই। তারপর `a % b == 0` সরাসরি বলে দেয় remainder শূন্য কিনা।
```
def digit_sum(n):
...
while n > 0:
s += n % 10
n //= 10
```
Level 0 (002)-এর সেই digit-extraction loop, হুবহু পুনর্ব্যবহার — last digit তুলে যোগ, তারপর ফেলে দাও। rule of 3/9-এ এই যোগফলটাই লাগবে।
```
def is_div_by_3(n):
return digit_sum(n) % 3 == 0
```
rule of 3 — পুরো `n` ভাগ না করে, তার digit sum 3 দিয়ে যায় কিনা দেখি। (গাণিতিকভাবে এরা সমতুল্য, কারণ `10 ≡ 1 mod 3`।)
```
def is_div_by_5(n):
return n % 10 in (0, 5)
```
rule of 5 — শুধু last digit (`n % 10`, Level 0-এর 008) দেখি, সেটা 0 বা 5 হলেই ভাগ যায়।
`for n in [...]` loop-টা গুরুত্বপূর্ণ — প্রতিটা rule-কে সরাসরি `n % 3` ইত্যাদির সাথে মিলিয়ে যাচাই করে যে rule সত্যিই ঠিক। এই "সরল দিয়ে চালাক verify" অভ্যাস। সব মিললে শেষে `সব test pass!`।
### Output মিলিয়ে দেখা {#14-output-walkthrough}
চালালে ছাপবে:
```text
True
True
True
সব test pass!
```
তিনটা লাইন তিনটা `print` থেকে: `divides(12, 4)` → True, `is_div_by_3(123)` → True (digit sum 6), `is_div_by_5(45)` → True (last digit 5)। তার আগে সব `assert` — মূল চেক, edge case (0, b=1, b=0), আর 10টা সংখ্যায় চারটে rule-এর সরাসরি যাচাই — চুপচাপ pass করেছে। শেষ লাইন `সব test pass!` মানে rule-গুলো সব ক্ষেত্রে সঠিক।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#15-time-complexity}
- **মূল `divides`:** **O(1)** — একটাই `%` operation।
- **rule of 3/9:** **O(log₁₀ n)** — digit sum বের করতে digit সংখ্যার সমান (≈ `log₁₀ n`) কাজ। rule of 2/5/10 আবার O(1) (শুধু last digit/bit)।
(মানে rule গুলো সরাসরি `n % 3`-এর চেয়ে algorithm-এ দ্রুত নয়; এদের আসল মূল্য হাতে-কলমে দ্রুত আঁচ করায়, আর modular arithmetic বোঝায়।)
### অতিরিক্ত জায়গা {#16-space-complexity}
**O(1)** — সব function-এ শুধু গুটিকয় variable (`s`, `n`)। কোনো list বা array নেই, সংখ্যার আকারের সাথে স্মৃতি বাড়ে না।
### যে ভুলগুলো এড়াতে হবে {#17-common-mistakes}
1. **`b = 0` ভুলে যাওয়া** — `a % 0` Python-এ `ZeroDivisionError` ছোঁড়ে। divisibility চেকে আগে `if b == 0` আটকাও (0 দিয়ে ভাগ অসংজ্ঞায়িত)।
2. **0-এর divisibility নিয়ে দ্বিধা** — `0 % 5 == 0`, তাই **0 সব সংখ্যার গুণিতক** (0-কে যেকোনো কিছু দিয়ে ভাগ যায়)। কিন্তু কেউ 0 *দিয়ে* ভাগ যায় না।
3. **rule of 3 আর 9 গুলিয়ে ফেলা** — digit sum 3 দিয়ে গেলে 3-এর গুণিতক, কিন্তু 9-এর গুণিতক হতে digit sum 9 দিয়ে যেতে হবে। `123`-এর digit sum 6 → 3-এ যায়, 9-এ যায় না।
4. **negative-এ rule প্রয়োগ** — rule গুলো সাধারণত positive সংখ্যায় ভাবা; negative-এ `abs()` নিয়ে digit দেখা নিরাপদ (এখানে `digit_sum`-এ `abs` আছে)।
5. **`==` আর `=` গুলিয়ে ফেলা** — `a % b = 0` লিখলে error; তুলনায় `==`।
## শেখা ও পরের অনুশীলন {#practice}
### এই ধারণার পরের অনুশীলন {#18-harder-problems-that-inherit-this-idea}
- **012 — Count Factors** (এই repo) — সংখ্যাটার সব divisor গোনা; প্রতিটা সম্ভাব্য divisor-এর জন্য এই `a % b == 0` চেক-ই ভিত্তি।
- **LeetCode — Fizz Buzz** (