Problem link ও উৎস
- **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-এর সাথে প্রথম পরিচয়)
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#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, এমনকি ভাগ — সব দাঁড়িয়ে যাবে।
### Input ও output {#6-example-input-and-output}
```text
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-এর উদাহরণ:
```text
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** দেয় (এটা একটা আশীর্বাদ, পরে দেখবে)।
### চেনা উদাহরণে বোঝা {#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)`।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#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-এ দেখছ।
### ভেতরের অঙ্ক {#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` দিয়ে ভাগ যায়। ঘড়ির ভাষায়: দুজন একই ঘরে দাঁড়িয়ে।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#7-brute-force-thinking}
`%` operator না জানলে remainder কীভাবে বের করতে? "হাতে গুনে" — `a` থেকে বারবার `m` বিয়োগ করতে থাকো যতক্ষণ না `0` থেকে `m−1`-এর মধ্যে কিছু থাকে:
```python
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।
```text
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` যত বড়ই হোক।
```python
def remainder(a, m):
return a % m
```
আর "একই ঘরে কিনা" (congruent) জানতে দুজনের remainder মেলালেই হলো:
```python
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-এ বাঁচাবে।
### ছবিতে বোঝা {#5-visual-explanation}
প্রথমে number line-কে ভাঁজ করে ঘড়ি বানানো — `m = 5` ধরে:
```text
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-এর ছবি — পেছনে হাঁটা:
```text
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-এর মধ্যে; ঘড়ি কখনো ঘরের বাইরে যায় না।
### ছোট input-এ ধাপে ধাপে {#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 — এক লাইনে:
```text
17 % 5 -> 17 = 5×3 + 2 -> remainder 2
```
দুটোই বলছে 2। একই সত্য, কিন্তু `%` সোজা উত্তরে নিয়ে গেল।
এবার negative `a = -3`, `m = 5` — Python কীভাবে দেখে:
```text
-3 % 5 -> -3 = 5×(-1) + 2 -> Python quotient floor করে (-1), remainder 2
```
## কোড ও ব্যাখ্যা {#code}
### Python {#12-python-solution}
```python
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}
```text
def remainder(a, m):
return a % m
```
এটাই হৃদয়। `a % m` সরাসরি Python-এর modulo — `m > 0` হলে উত্তর 0 থেকে m−1-এর মধ্যে, এমনকি `a` negative হলেও non-negative।
```text
def remainder_safe(a, m):
return ((a % m) + m) % m
```
ভাষা-নিরপেক্ষ রূপ। ভেতরের `a % m`-এ যদি কোনো ভাষায় negative আসত, `+ m` করে আবার `% m` নিলে সেটা 0 থেকে m−1-এ চলে আসে। Python-এ এমনিতেই ঠিক, তাই এটা একই উত্তর — কিন্তু অভ্যাস গড়ার জন্য রাখা।
```text
def congruent(a, b, m):
return a % m == b % m
```
দুজনের remainder সমান কিনা মেলায়। সমান মানে একই ঘরে — congruent। `==` একটা True/False expression, তাই সরাসরি return।
বাকি `assert` লাইনগুলো নিজেদের চেক করছে — উত্তর আশানুরূপ না হলে program সেখানেই থেমে error দেবে। সব ঠিক থাকলে শেষে `সব test pass!` ছাপে।
### Output মিলিয়ে দেখা {#14-output-walkthrough}
চালালে যা ছাপবে:
```text
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!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#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 হয়ে ফিরবে।
## শেখা ও পরের অনুশীলন {#practice}
### এই ধারণার পরের অনুশীলন {#18-harder-problems-that-inherit-this-idea}
- **CSES — Exponentiation** (