026 — Remainder Basics

এই note দিয়ে তুমি Level 2-এর দরজায় পা রাখছ। Level 0-তে % ছিল last digit বের করার কাঁচি, Level 1-এ divisibility-র পরীক্ষক। এখন একই %-কে নতুন চোখে দেখব — একটা ঘড়ি, যেখানে সংখ্যা ঘুরে ঘুরে ছোট পরিসরে নেমে আসে। ধীরে পড়ো, ঘড়ির ছবিটা আগে মাথায় বসাও।

Source

• Original source: Classic exercise (modular arithmetic-এর একদম গোড়ার অনুশীলন)
• Platform: Classic exercise — কোনো একক judge নেই; প্রায় সব CP intro-তে থাকে
• Topic: Math-based programming fundamentals → Level 2: Modular Arithmetic
• Difficulty: Easy
• Pattern: mod basics (remainder + congruence)
• Basic idea inherited from: 001 — Even or Odd (% operator-এর সাথে প্রথম পরিচয়)

1. Problem in simple words

দুটো integer a আর m দেওয়া আছে (m > 0)। বলতে হবে a-কে m দিয়ে ভাগ করলে কত remainder (বাকি) থাকে — মানে a % m।

সঙ্গে আরও দুটো ছোট প্রশ্ন একই গোত্রের:

• দুটো সংখ্যা a আর b কি একই remainder দেয় m দিয়ে? (একে বলে congruent mod m)
• a যদি negative হয়, remainder কত হওয়া উচিত — আমরা চাই সবসময় 0 থেকে m−1 এর মধ্যে একটা non-negative উত্তর।

দেখতে তুচ্ছ, কিন্তু এই remainder-ই পুরো Level 2-এর ভিত। ঠিকঠাক বুঝলে যোগ, গুণ, power, এমনকি ভাগ — সব দাঁড়িয়ে যাবে।

2. What is the math idea?

মূল idea হলো division with remainder আর তার থেকে আসা modular arithmetic।

যেকোনো integer a আর positive m-এর জন্য ঠিক একভাবে লেখা যায়:

a = q × m + r, যেখানে 0 ≤ r < m

এখানে q হলো quotient (ভাগফল), r হলো remainder (বাকি)। সেই r-ই a % m।

আর congruence: a ≡ b (mod m) মানে a আর b-কে m দিয়ে ভাগ করলে remainder একই — অর্থাৎ (a − b) পুরোপুরি m দিয়ে ভাগ যায়। ঘড়ির ভাষায়: দুজন একই ঘরে দাঁড়িয়ে।

3. Which basic idea does this inherit from?

এটা সরাসরি 001 — Even or Odd থেকে এসেছে। সেখানে তুমি n % 2 দিয়ে শিখেছিলে remainder বলে দেয় "কী বাকি রইল"। % 2 ছিল মাত্র দুই ঘরের ঘড়ি (0 আর 1)।

এখন সেই একই idea-কে generalize করছি: 2-এর জায়গায় যেকোনো m। % 2 → % m। দুই ঘরের ঘড়ি → m ঘরের ঘড়ি। even/odd-এর parity ছিল mod 2-এর special case; remainder basics হলো তার পূর্ণ রূপ।

মানে আজ তুমি নতুন কিছু শিখছ না, বরং চেনা %-কে আরও বড় canvas-এ দেখছ।

4. Real-life analogy

ভাবো একটা 12 ঘণ্টার ঘড়ি। এখন 9টা বাজে। 5 ঘণ্টা পরে কয়টা? অঙ্কে 9 + 5 = 14, কিন্তু ঘড়ি বলে 2টা — কারণ কাঁটা 12 পেরিয়ে আবার শুরু থেকে গোনে।

এই "12 পেরোলেই আবার 0 থেকে" — এটাই % 12। 14 % 12 = 2।

remainder মানে: পুরো চক্কর (12, 24, 36...) বাদ দিয়ে কাঁটা শেষ পর্যন্ত কোন ঘরে দাঁড়াল। আর negative? ঘড়িতে পেছনে হাঁটা — 12টা থেকে 3 ঘণ্টা পিছালে 9টা, তাই −3 ≡ 9 (mod 12)।

5. Visual explanation

প্রথমে number line-কে ভাঁজ করে ঘড়ি বানানো — m = 5 ধরে:

mod 5 এর ঘড়ি (5টা ঘর: 0,1,2,3,4):

number line:  0  1  2  3  4 | 5  6  7  8  9 | 10 11 12 13 14
remainder:    0  1  2  3  4 | 0  1  2  3  4 |  0  1  2  3  4
              ^একটা চক্কর^   ^আবার শুরু^      ^আবার শুরু^

7 % 5 = 2,  12 % 5 = 2,  2 % 5 = 2  ->  7, 12, 2 ঘড়ির একই ঘরে (congruent)

এবার negative-এর ছবি — পেছনে হাঁটা:

mod 5 এ পেছনে হাঁটা:

  ... -3  -2  -1 |  0   1   2   3   4
  ...  2   3   4 |  0   1   2   3   4
       ^                 
   -3 % 5 = 2  (5 ঘরের ঘড়িতে 3 ঘর পিছালে 2-তে পৌঁছাই)

খেয়াল করো — উত্তর সবসময় 0 থেকে 4-এর মধ্যে; ঘড়ি কখনো ঘরের বাইরে যায় না।

6. Example input and output

a      m   ->  a % m        ব্যাখ্যা
--------------------------------------------------
17     5   ->  2            17 = 5×3 + 2
20     4   ->  0            20 = 4×5 + 0 (নিঃশেষে ভাগ)
3      7   ->  3            a < m, পুরোটাই remainder
-3     5   ->  2            Python: পেছনে 3 ঘর -> 2
-7     3   ->  2            -7 = 3×(-3) + 2
0      9   ->  0            0 যেকোনো কিছু দিয়ে ভাগে 0

congruence-এর উদাহরণ:

17 ≡ 2 (mod 5)?   17 % 5 = 2, 2 % 5 = 2  ->  হ্যাঁ, congruent
17 ≡ 3 (mod 5)?   17 % 5 = 2, 3 % 5 = 3  ->  না

দুটো জিনিস মনে রাখো: a < m হলে remainder পুরো a-ই; আর Python-এ negative % সবসময় non-negative দেয় (এটা একটা আশীর্বাদ, পরে দেখবে)।

7. Brute force thinking

% operator না জানলে remainder কীভাবে বের করতে? "হাতে গুনে" — a থেকে বারবার m বিয়োগ করতে থাকো যতক্ষণ না 0 থেকে m−1-এর মধ্যে কিছু থাকে:

def remainder_brute(a, m):
    if a >= 0:
        while a >= m:
            a -= m          # একটা চক্কর সরিয়ে রাখলাম
        return a
    else:
        while a < 0:
            a += m          # negative হলে উল্টো দিকে, non-negative করতে
        return a

এটা আসলে ঘড়ির কাঁটা এক এক ঘর করে ঘোরানোর মতো — যতক্ষণ না ঠিক ঘরে পৌঁছাই। ঠিক উত্তরই দেয়।

8. Why brute force may be slow

সমস্যা: loop ঘোরে প্রায় a / m বার। a = 1,000,000,000 আর m = 3 হলে loop প্রায় 33 কোটি বার চলবে — interview-তে এটা সরাসরি Time Limit Exceeded।

a = 1000000000, m = 3 হলে:
  brute force: ~333000000 বার বিয়োগ  (ধীর, O(a/m))
  smart way  : ঠিক 1 বার %           (চোখের নিমেষে, O(1))

মূল শিক্ষা: যেটা division-এর একটা operation-এ জানা যায়, তার জন্য বিয়োগের loop চালানো অপচয়। আমাদের কাছে সেই এক-ধাপের tool আছে — %।

9. Better thinking

সরাসরি জিজ্ঞেস করি: "m দিয়ে ভাগ করলে কত বাকি?" সেটাই a % m। একটাই operation, a যত বড়ই হোক।

def remainder(a, m):
    return a % m

আর "একই ঘরে কিনা" (congruent) জানতে দুজনের remainder মেলালেই হলো:

def congruent(a, b, m):
    return a % m == b % m

এটাই O(1) — constant time। brute force-এর কোটি কোটি বিয়োগ এক ধাপে নেমে এল।

10. Thinking tweak

আসল "আহা!" মুহূর্ত: remainder মানে চক্কর ফেলে দিয়ে শুধু "শেষ অবস্থান"। পুরো a কত বড় তাতে কিছু আসে যায় না — m-এর কতগুলো পূর্ণ চক্কর হলো সেটা ভুলে যাও, শুধু ঘড়ির কাঁটা কোথায় থামল সেটাই উত্তর।

আর negative-এর tweak: যদি কখনো ভাষা-নিরপেক্ষ safe উত্তর চাও (C++-এ % negative দিতে পারে), এই রূপটা মনে রাখো —

((a % m) + m) % m

এটা সবসময় 0 থেকে m−1-এর মধ্যে non-negative দেয়। Python-এ এমনিতেই ঠিক, কিন্তু এই অভ্যাসটা পরের সব problem-এ বাঁচাবে।

11. Step-by-step dry run

চলো a = 17, m = 5 ধীরে চালাই — আগে brute force (চক্কর সরানো):

step	a (শুরুতে)	a >= 5?	a -= 5	হাতে রইল
1	17	হ্যাঁ	17 - 5 = 12	12
2	12	হ্যাঁ	12 - 5 = 7	7
3	7	হ্যাঁ	7 - 5 = 2	2
4	2	না (loop থামল)	—	2

তিনটে পূর্ণ চক্কর (5×3 = 15) সরিয়ে হাতে রইল 2।

এবার smart way — এক লাইনে:

17 % 5  ->  17 = 5×3 + 2  ->  remainder 2

দুটোই বলছে 2। একই সত্য, কিন্তু % সোজা উত্তরে নিয়ে গেল।

এবার negative a = -3, m = 5 — Python কীভাবে দেখে:

-3 % 5  ->  -3 = 5×(-1) + 2  ->  Python quotient floor করে (-1), remainder 2

12. Python solution

def remainder(a, m):
    """a-কে m দিয়ে ভাগ করলে remainder (Python: সবসময় non-negative যদি m > 0)।"""
    return a % m


def remainder_safe(a, m):
    """ভাষা-নিরপেক্ষ non-negative remainder (C++-এও কাজ করবে এমন রূপ)।"""
    return ((a % m) + m) % m


def congruent(a, b, m):
    """a আর b কি একই remainder দেয় m দিয়ে? (a ≡ b mod m)"""
    return a % m == b % m


# --- ছোট test গুলো (সব pass করা উচিত) ---
assert remainder(17, 5) == 2
assert remainder(20, 4) == 0
assert remainder(3, 7) == 3
assert remainder(-3, 5) == 2            # Python: non-negative
assert remainder(0, 9) == 0

assert remainder_safe(-3, 5) == 2
assert remainder_safe(-7, 3) == 2
assert remainder_safe(17, 5) == 2       # positive-এও একই উত্তর

assert congruent(17, 2, 5) is True      # 17 ≡ 2 (mod 5)
assert congruent(17, 3, 5) is False
assert congruent(-3, 2, 5) is True      # -3 আর 2 একই ঘরে

print(remainder(17, 5))         # 2
print(remainder_safe(-3, 5))    # 2
print(congruent(17, 2, 5))      # True
print("সব test pass!")

13. Line-by-line explanation

def remainder(a, m):
    return a % m

এটাই হৃদয়। a % m সরাসরি Python-এর modulo — m > 0 হলে উত্তর 0 থেকে m−1-এর মধ্যে, এমনকি a negative হলেও non-negative।

def remainder_safe(a, m):
    return ((a % m) + m) % m

ভাষা-নিরপেক্ষ রূপ। ভেতরের a % m-এ যদি কোনো ভাষায় negative আসত, + m করে আবার % m নিলে সেটা 0 থেকে m−1-এ চলে আসে। Python-এ এমনিতেই ঠিক, তাই এটা একই উত্তর — কিন্তু অভ্যাস গড়ার জন্য রাখা।

def congruent(a, b, m):
    return a % m == b % m

দুজনের remainder সমান কিনা মেলায়। সমান মানে একই ঘরে — congruent। == একটা True/False expression, তাই সরাসরি return।

বাকি assert লাইনগুলো নিজেদের চেক করছে — উত্তর আশানুরূপ না হলে program সেখানেই থেমে error দেবে। সব ঠিক থাকলে শেষে সব test pass! ছাপে।

14. Output walkthrough

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

2
2
True
সব test pass!

প্রথম লাইন remainder(17, 5) থেকে → 2। দ্বিতীয় লাইন remainder_safe(-3, 5) থেকে → 2 (negative হলেও non-negative)। তৃতীয় লাইন congruent(17, 2, 5) → True (দুজনেই remainder 2)। তার আগের সব assert চুপচাপ pass করেছে। সবশেষে সব test pass!।

15. Time complexity

O(1) — একটাই % operation, a বা m যত বড়ই হোক। সংখ্যার মানের সাথে কাজ বাড়ে না।

(সূক্ষ্ম কথা: অতি-বিশাল সংখ্যায় modulo-র খরচ digit সংখ্যার সাথে সামান্য বাড়ে, কিন্তু সাধারণ interview-র মাপে একে নিশ্চিন্তে O(1) ধরি — brute force-এর O(a/m)-এর তুলনায় আকাশ-পাতাল পার্থক্য।)

16. Space complexity

O(1) — কোনো list, array লাগছে না; শুধু গুটিকয় variable। input ছাড়া আলাদা জায়গা প্রায় শূন্য।

17. Common mistakes

• negative remainder নিয়ে ভাষার পার্থক্য ভুলে যাওয়া — Python-এ -3 % 5 == 2, কিন্তু C++/Java-তে -3 % 5 == -3। ভাষা-নিরপেক্ষ safe রূপ ((a % m) + m) % m মনে রাখো।
• m = 0 ভুলে যাওয়া — 0 দিয়ে ভাগ অসংজ্ঞায়িত; Python ZeroDivisionError দেবে। সবসময় ধরে নাও m > 0।
• congruence-কে সমতা ভাবা — 17 ≡ 2 (mod 5) মানে 17 আর 2 সমান নয়; শুধু একই ঘরে। == নয়, remainder মেলানো।
• a < m হলে remainder 0 ভাবা — না, তখন remainder পুরো a-ই (যেমন 3 % 7 = 3)।
• m = 1 ভুলে যাওয়া — যেকোনো সংখ্যা mod 1 = 0 (এক ঘরের ঘড়ি)। পরের problem-এ এটা edge case হয়ে ফিরবে।

18. Harder problems that inherit this idea

• CSES — Exponentiation (https://cses.fi/problemset/task/1095) — এই remainder-এর উপরেই fast power দাঁড়ায়; প্রতি step-এ % m নেওয়াটা এখানকার সরাসরি বিস্তার।
• 031 (Large Number Mod) — বিশাল সংখ্যার remainder digit-by-digit; এই basic remainder + Level 0-এর digit loop একসাথে।
• 037 (Clock Arithmetic Problems) — এই note-এর ঘড়ি analogy-টাই পুরো একটা problem হয়ে ফিরবে।

19. Pattern learned

Remainder + congruence as a clock — a % m মানে চক্কর ফেলে দিয়ে ঘড়ির শেষ অবস্থান (0 থেকে m−1)। আর a ≡ b (mod m) মানে দুজন একই ঘরে। negative-এ safe রূপ ((a % m) + m) % m। এই ঘড়ির ছবিটাই পুরো Level 2-এর ভিত।

20. Final summary

ভবিষ্যতের আমাকে এক লাইনে: "remainder = m-ঘরের ঘড়িতে কাঁটার শেষ অবস্থান; a % m দিয়ে এক ধাপে পাই; negative হলে ((a%m)+m)%m safe; congruent মানে একই ঘর। % 2 ছিল এর শিশু-রূপ।"

পরের ধাপ → 027 — Modular Addition (এই ঘড়িতে যোগ করলে কী হয়)। সম্পর্কিত → 037 — Clock Arithmetic Problems, 031 — Large Number Mod।

ফিরে দেখা: এই 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" / "CP-তে নিত্য দরকারি" লেখা।