011 — Divisibility Rules

স্বাগতম Level 1-এ! Level 0-তে তুমি % দিয়ে একটা সংখ্যার ভেতরে হেঁটেছ। এখন সেই %-কেই নতুন চোখে দেখব — দুটো সংখ্যার সম্পর্ক হিসেবে: একটা আরেকটাকে নিঃশেষে ভাগ করে কিনা। আর সাথে শিখব সেই চেনা স্কুল-নিয়মগুলো (2 দিয়ে ভাগ যায় কিনা last digit দেখে, 3 দিয়ে digit sum দেখে) — যেগুলো আসলে কেন কাজ করে, সেটাও বুঝব। এই divisibility-র ধারণাই পুরো level-এর ভিত্তি; factor, prime, GCD — সব এর উপর দাঁড়িয়ে।

Source

• 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)

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-ও শিখব।

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-তে পুরো প্রমাণ দেখব), কিন্তু এখন ব্যবহারটাই শিখি।

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-গুলোও আবছা থাকবে।

4. Real-life analogy

ভাবো তোমার কাছে aটা চকলেট, আর তুমি b জন বন্ধুর মধ্যে সমানভাবে ভাগ করতে চাও।

• সবাই সমান পেল, হাতে একটাও রইল না → a % b == 0 → ভাগ যায় (ঝগড়াহীন ভাগ)
• সমান ভাগের পরেও কিছু চকলেট হাতে রয়ে গেল → সেই বাকি অংশই remainder → ভাগ যায় না

যেমন 12টা চকলেট 4 জনকে দিলে প্রত্যেকে 3টা, হাতে শূন্য — শান্তি। কিন্তু 5 জনকে দিলে প্রত্যেকে 2টা, হাতে 2টা বাকি — সেই 2টা নিয়ে টানাটানি। Divisibility মানে হাতে কিছু না থাকা ভাগ।

আর rule-গুলো? সেগুলো হলো শর্টকাট — পুরো ভাগ না করেই আগেভাগে আঁচ করা "এই ভাগটা মসৃণ হবে কিনা"।

5. Visual explanation

a % b কে "বারবার b সরিয়ে শেষে কী বাকি" ভাবো — 12 ÷ 4 আর 12 ÷ 5 পাশাপাশি:

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 দিয়ে ভাগ যায়?):

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-এর সৌন্দর্য।

6. Example input and output

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)।

7. Brute force thinking

মূল divisibility চেক তো সরল — a % b == 0। কিন্তু ধরো % operator নেই, বা rule-গুলো হাতে যাচাই করতে চাও। তখন "হাতে গুনে" করার ভাবনা — b বারবার যোগ করে দেখো ঠিক a-তে পৌঁছায় কিনা:

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 এক ধাপে উত্তর দিত।

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

মূল চেক সরাসরি % দিয়ে — এক ধাপ:

def divides(a, b):
    if b == 0:
        return False           # 0 দিয়ে ভাগ অসংজ্ঞায়িত
    return a % b == 0

আর rule-গুলো digit ব্যবহার করে (Level 0-এর digit-extraction এখানে কাজে লাগে):

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 মাথায় গাঁথো।

11. Step-by-step dry run

প্রথমে divides(12, 4) — smart version এক ধাপ:

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-এর নির্ভরযোগ্যতার প্রমাণ।

12. Python solution

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!।

14. Output walkthrough

চালালে ছাপবে:

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-গুলো সব ক্ষেত্রে সঠিক।

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; তুলনায় ==।

18. Harder problems that inherit this idea

• 012 — Count Factors (এই repo) — সংখ্যাটার সব divisor গোনা; প্রতিটা সম্ভাব্য divisor-এর জন্য এই a % b == 0 চেক-ই ভিত্তি।
• LeetCode — Fizz Buzz (https://leetcode.com/problems/fizz-buzz/) — 3 আর 5 দিয়ে ভাগ যায় কিনা (% 3, % 5) — সরাসরি divisibility-র classic প্রয়োগ।
• CSES — Divisor Analysis / Project Euler-এর অনেক problem — বড় সংখ্যায় divisibility আর factor গোনার উপর দাঁড়িয়ে।

19. Pattern learned

Divisibility = a % b == 0 — ভাগফল নয়, remainder শূন্য কিনা সেটাই আসল। আর divisibility rules: কিছু ভাজকের জন্য (2/5/10 → last digit, 3/9 → digit sum) পুরো ভাগ না করেই উত্তর। বড় শিক্ষা: % শুধু একটা সংখ্যার ভেতরের tool নয়, দুটো সংখ্যার সম্পর্ক মাপারও tool — আর এই সম্পর্কই factor, prime, GCD সব কিছুর ভিত্তি।

20. Final summary

ভবিষ্যতের আমাকে এক লাইনে: "divisibility = a % b == 0 (আগে b != 0 নিশ্চিত করো)। 2/5/10 → last digit দেখো, 3/9 → digit sum দেখো (কারণ 10 ≡ 1 mod 3,9)। 0 সবার গুণিতক, কিন্তু 0 দিয়ে ভাগ নয়। এটা 001-এর even/odd-এরই বড় রূপ।"

আগের শিকড় → 001 — Even or Odd (2 দিয়ে ভাগ — divisibility-র প্রথম রূপ)। পরের ধাপ → 012 — Count Factors (এই চেক দিয়ে সব divisor গোনা)।

ফিরে দেখা: এই level-এর map → ../README.md · concept ঝালাই → ../concept-notes.md · এই note-টা যে ছকে লেখা → ../../../templates/math-problem-note-template.md।

---

মনে রাখার নিয়ম (legal): সব নিজের ভাষায় লেখা; problem statement copy করা হয়নি; official link শুধু attribution-এর জন্য রাখা; "asked by Google/Amazon" এমন দাবি করা হয়নি — বরং "common interview pattern" হিসেবে লেখা।