Problem link ও উৎস
- **Original source:** Classic exercise (modular arithmetic-এর যোগের নিয়ম)
- **Platform:** Classic exercise — প্রায় সব CP intro আর textbook-এ থাকে
- **Topic:** Math-based programming fundamentals → Level 2: Modular Arithmetic
- **Difficulty:** Easy
- **Pattern:** (a+b)%m (modular addition / subtraction)
- **Basic idea inherited from:** 026 — Remainder Basics (clock model + remainder)
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
দুটো (বা অনেকগুলো) integer আর একটা `m` দেওয়া। বলতে হবে তাদের **যোগফল mod m** — মানে `(a + b) % m`।
আসল challenge: `a` আর `b` এত বড় হতে পারে যে যোগফল রাখা কঠিন/ধীর (C++/Java-তে overflow, Python-এ বিশাল সংখ্যা slow)। তাই আমরা চাই — পুরো যোগফল না বানিয়ে, প্রতি step-এ `m`-এর ঘড়িতে নামিয়ে নিয়ে কাজ করতে।
আর বিয়োগ: `(a − b) % m` — যেটা negative হয়ে যেতে পারে, সেটাকে non-negative রাখা।
### Input ও output {#6-example-input-and-output}
```text
a b m -> (a+b)%m ব্যাখ্যা
-----------------------------------------------------
9 8 12 -> 5 17 % 12 = 5
100 50 12 -> 6 150 % 12 = 6
7 3 5 -> 0 10 % 5 = 0
999999 999999 7 -> 2 (চাইলে নিজে মিলাও)
```
বিয়োগ:
```text
a b m -> (a-b)%m (non-negative)
-----------------------------------------------------
3 5 12 -> 10 -2 -> 10
5 3 12 -> 2 2 -> 2
0 1 5 -> 4 -1 -> 4
```
খেয়াল করো বিয়োগে উত্তর negative হতে পারে — আমরা সবসময় 0 থেকে m−1-এ টেনে আনি।
### চেনা উদাহরণে বোঝা {#4-real-life-analogy}
আবার সেই **12 ঘণ্টার ঘড়ি**। এখন 9টা বাজে, তুমি আরও 8 ঘণ্টা যোগ করবে। 9 + 8 = 17 — কিন্তু ঘড়ি বলে **5টা** (`17 % 12 = 5`)।
এখন ধরো তুমি 9 আর 8 আগেই ঘড়ির হিসাবে ভেবে নিলে: 9 তো ঘড়িতেই 9, 8-ও 8। যোগ করলে 17, আবার ঘড়িতে নামালে 5 — একই উত্তর। বড় সংখ্যা হলেও — যেমন 100 + 50 ঘণ্টা: `100 % 12 = 4`, `50 % 12 = 2`, `(4 + 2) % 12 = 6`; আর সরাসরি `150 % 12 = 6`। **মিলে গেল!** এই "আগে ছোট করে নাও" চালাকিই modular addition।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#3-which-basic-idea-does-this-inherit-from}
সরাসরি **026 — Remainder Basics** থেকে। 026-এ শিখেছ একটা সংখ্যাকে ঘড়ির ঘরে নামানো (`a % m`)। এখন দুটো সংখ্যাকে নামিয়ে **যোগ করা**।
026-এর `((a % m) + m) % m` (negative-safe রূপ) এখানে সরাসরি কাজে আসবে বিয়োগের বেলায়। মানে remainder-এর basic বোঝাপড়াটাই এখানে দুই-অপারেন্ডে বিস্তৃত হলো।
আর শিকড়ে ফিরলে — 001-এর `% 2` ছিল এক সংখ্যার parity; 026 generalize করল; 027 তাতে যোগ যোগ করল।
### ভেতরের অঙ্ক {#2-what-is-the-math-idea}
মূল idea — **modular addition rule**:
`(a + b) % m = ((a % m) + (b % m)) % m`
মানে যোগের *আগে* দুজনকে আলাদা আলাদা ঘড়ির ঘরে নামিয়ে নিলেও শেষ উত্তর একই।
কেন? `a = q₁m + r₁`, `b = q₂m + r₂` লিখলে `a + b = (q₁+q₂)m + (r₁+r₂)`। এখানে `(q₁+q₂)m` অংশটা `m`-এর গুণিতক — ঘড়িতে পুরো পুরো চক্কর, কাঁটার অবস্থানে কোনো প্রভাব নেই। কাঁটা কোথায় থামবে তা ঠিক করে শুধু `(r₁ + r₂)`।
বিয়োগেও একই: `(a − b) % m = ((a % m) − (b % m)) % m`, তবে এখানে ফল negative হতে পারে।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#7-brute-force-thinking}
সবচেয়ে সরল: পুরো যোগফল বানিয়ে শেষে একবার mod নাও।
```python
def add_mod_brute(a, b, m):
total = a + b # পুরো যোগফল — যত বড়ই হোক
return total % m
```
অনেকগুলো সংখ্যা হলে সবগুলো যোগ করে শেষে একবার mod:
```python
def sum_mod_brute(nums, m):
return sum(nums) % m # আগে পুরো sum, তারপর mod
```
Python-এ এটা ঠিক উত্তর দেয় (unbounded int)। কিন্তু এখানেই সমস্যার বীজ।
### কোথায় বেশি কাজ হতে পারে {#8-why-brute-force-may-be-slow}
দুটো আলাদা সমস্যা:
1. **C++/Java-তে overflow:** `a + b` যদি 64-bit সীমা (~9.2×10¹⁸) ছাড়ায়, যোগফল wrap করে garbage হয় — তারপর mod নিলেও ভুল উত্তর।
2. **Python-এ slowness:** int unbounded, overflow নেই — কিন্তু লক্ষ লক্ষ বিশাল সংখ্যা যোগ করলে মাঝের সংখ্যাগুলো প্রকাণ্ড হয়ে যায়, প্রতিটা যোগ ক্রমশ ধীর।
```text
1000টা সংখ্যা, প্রতিটা ~10^18:
brute: sum আগে -> মাঝের total ~10^21, বড় সংখ্যার যোগ ধীর
smart: প্রতি যোগের পরেই % m -> সংখ্যা কখনো 2m ছাড়ায় না, দ্রুত
```
মূল শিক্ষা: বড় হওয়ার সুযোগই দিও না — প্রতি step-এ ছোট করে রাখো।
### আরও ভালোভাবে ভাবা {#9-better-thinking}
modular addition rule কাজে লাগাই — প্রতি যোগের পরেই mod:
```python
def add_mod(a, b, m):
return ((a % m) + (b % m)) % m
```
list-এর জন্য প্রতি step-এ mod নিয়ে জমাও:
```python
def sum_mod(nums, m):
total = 0
for x in nums:
total = (total + x) % m # প্রতি step-এ ঘড়িতে নামাও
return total
```
এখন `total` কখনো `2m`-এর বেশি বড় হয় না — ছোট, দ্রুত, overflow-মুক্ত।
বিয়োগে negative-safe রূপ:
```python
def sub_mod(a, b, m):
return ((a % m) - (b % m) + m) % m
```
### ভাবনার পরিবর্তন {#10-thinking-tweak}
আসল "আহা!": **সংখ্যা বড় হওয়ার অপেক্ষা কোরো না — প্রতিটা যোগের পরপরই `% m` নাও।** তাতে মাঝের কোনো সংখ্যাই `m`-এর ধারেকাছের বেশি বড় হয় না।
আর বিয়োগের tweak: বিয়োগে ফল negative হতে পারে, তাই `% m` করার আগে `+ m` যোগ করে নাও — `(... + m) % m`। এই "+m তারপর %m" রূপটা পুরো Level 2-এ negative সামলানোর মন্ত্র।
### ছবিতে বোঝা {#5-visual-explanation}
`m = 12` ধরে, যোগের আগে-পরে mod নেওয়া একই ফল দেয় তা দেখি:
```text
(100 + 50) % 12 দুই রাস্তায়:
রাস্তা A (সরাসরি): 100 + 50 = 150 -> 150 % 12 = 6
রাস্তা B (প্রতি step):
100 % 12 = 4
50 % 12 = 2
(4 + 2) % 12 = 6
^ একই উত্তর! কিন্তু সংখ্যা কখনো 6+11=17 ছাড়াল না
```
বিয়োগে negative সামলানোর ছবি (`(3 - 5) % 12`):
```text
3 - 5 = -2 -> Python: -2 % 12 = 10 (ঘড়িতে 3 থেকে 5 ঘর পিছালে 10)
ভাষা-নিরপেক্ষ safe রূপ:
((3 - 5) % 12 + 12) % 12 = (-2 + 12) % 12 = 10 % 12 = 10
কখনো negative ঘরে যায়নি
```
### ছোট input-এ ধাপে ধাপে {#11-step-by-step-dry-run}
`nums = [9, 8, 7]`, `m = 5` — প্রতি step-এ mod:
| step | x | total (আগে) | total + x | (total + x) % 5 |
| --- | --- | --- | --- | --- |
| শুরু | — | 0 | — | 0 |
| 1 | 9 | 0 | 9 | 9 % 5 = 4 |
| 2 | 8 | 4 | 12 | 12 % 5 = 2 |
| 3 | 7 | 2 | 9 | 9 % 5 = 4 |
উত্তর **4**। Check সরাসরি: 9 + 8 + 7 = 24, `24 % 5 = 4` ✓। লক্ষ করো — `total` কখনো 12-এর বেশি গেল না, যদিও সরাসরি যোগে 24 হতো।
বিয়োগ dry run `(3 - 5) % 5`:
```text
3 % 5 = 3, 5 % 5 = 0
(3 - 0 + 5) % 5 = 8 % 5 = 3
Check: 3 - 5 = -2, -2 % 5 = 3 ✓
```
## কোড ও ব্যাখ্যা {#code}
### Python {#12-python-solution}
```python
def add_mod(a, b, m):
"""(a + b) % m — প্রতি অপারেন্ড আগে ঘড়িতে নামিয়ে।"""
return ((a % m) + (b % m)) % m
def sub_mod(a, b, m):
"""(a - b) % m — non-negative রাখতে + m।"""
return ((a % m) - (b % m) + m) % m
def sum_mod(nums, m):
"""list-এর সব সংখ্যার যোগফল mod m — প্রতি step-এ mod।"""
total = 0
for x in nums:
total = (total + x) % m
return total
# --- ছোট test গুলো (সব pass করা উচিত) ---
assert add_mod(9, 8, 12) == 5 # 17 % 12
assert add_mod(100, 50, 12) == 6 # 150 % 12
assert add_mod(7, 3, 5) == 0 # 10 % 5
# brute-এর সাথে মিলিয়ে দেখা (যাচাই):
assert add_mod(999999, 999999, 7) == (999999 + 999999) % 7
assert sub_mod(3, 5, 12) == 10 # -2 -> 10
assert sub_mod(5, 3, 12) == 2
assert sub_mod(0, 1, 5) == 4 # -1 -> 4
assert sub_mod(3, 5, 12) == (3 - 5) % 12 # Python-এর সাথে মিল
assert sum_mod([9, 8, 7], 5) == 4 # 24 % 5
assert sum_mod([10**18, 10**18, 10**18], 7) == (3 * 10**18) % 7
print(add_mod(9, 8, 12)) # 5
print(sub_mod(3, 5, 12)) # 10
print(sum_mod([9, 8, 7], 5)) # 4
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#13-line-by-line-explanation}
```text
def add_mod(a, b, m):
return ((a % m) + (b % m)) % m
```
দুজনকে আগে আলাদা করে ঘড়িতে নামাই (`a % m`, `b % m`), যোগ করি, তারপর আবার `% m`। এতে মাঝের যোগফল কখনো `2m`-এর বেশি বড় হয় না।
```text
def sub_mod(a, b, m):
return ((a % m) - (b % m) + m) % m
```
বিয়োগে ফল negative হতে পারে, তাই `+ m` করে non-negative ঘরে টেনে আনি, তারপর `% m`। এটাই 026-এর negative-safe idea-র যোগ-বিয়োগ রূপ।
```text
def sum_mod(nums, m):
total = 0
for x in nums:
total = (total + x) % m
return total
```
`total`-এ প্রতিটা সংখ্যা যোগ করি, কিন্তু **প্রতি step-এই** `% m`। তাই `total` কখনো বড় হয় না — দ্রুত আর overflow-মুক্ত।
`assert ... == (999999 + 999999) % 7` লাইনগুলো brute force-এর সরাসরি যোগের সাথে মিলিয়ে দেখছে — mod-এর bug চোখে দেখা যায় না, এই মেলানোতেই ধরা পড়ে। সব ঠিক থাকলে শেষে `সব test pass!`।
### Output মিলিয়ে দেখা {#14-output-walkthrough}
চালালে যা ছাপবে:
```text
5
10
4
সব test pass!
```
প্রথম লাইন `add_mod(9, 8, 12)` → 5 (17 mod 12)। দ্বিতীয় `sub_mod(3, 5, 12)` → 10 (−2 কে non-negative করে)। তৃতীয় `sum_mod([9,8,7], 5)` → 4 (24 mod 5)। আগের সব `assert` চুপচাপ pass করেছে — তারপর `সব test pass!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#15-time-complexity}
- `add_mod`, `sub_mod`: **O(1)** — গুটিকয় mod আর যোগ।
- `sum_mod`: **O(n)** — `n` টা সংখ্যার উপর একবার করে loop, প্রতিবার O(1) কাজ।
brute force-এর তুলনায় Big-O একই (`sum`-ও O(n)), কিন্তু এখানে মাঝের সংখ্যা ছোট থাকায় constant factor অনেক কম আর overflow-নিরাপদ।
### অতিরিক্ত জায়গা {#16-space-complexity}
**O(1)** — input list ছাড়া শুধু একটা `total` variable। বাড়তি list/array লাগছে না।
### যে ভুলগুলো এড়াতে হবে {#17-common-mistakes}
- **শেষে একবারে mod নেওয়া** — `sum(nums) % m` Python-এ ঠিক উত্তর দেয় কিন্তু মাঝের সংখ্যা বিশাল হয়ে slow; C++/Java হলে overflow-এ ভুল। অভ্যাস: **প্রতি যোগের পরেই `% m`**।
- **বিয়োগে negative ভুলে যাওয়া** — `(a - b) % m` C++-এ negative দিতে পারে; safe রূপ `((a - b) % m + m) % m`।
- **`+ m` ভুল জায়গায়** — বিয়োগে `+ m` করতে হবে `% m`-এর *আগে*: `((a - b) + m) % m`, `((a - b) % m) + m` নয় (পরেরটা m-এর বেশি দিতে পারে যদি মাঝে আবার mod না নাও)।
- **mod 1 ভুলে যাওয়া** — সব কিছু mod 1 = 0; যোগফলও 0 হওয়া উচিত।
- **operand আগে mod না নিয়ে বিশাল রাখা** — `a` নিজেই বিশাল হলে `(a % m)` আগে নিলে নিরাপদ; সরাসরি `a + b` রাখলে C++-এ overflow।
## শেখা ও পরের অনুশীলন {#practice}
### এই ধারণার পরের অনুশীলন {#18-harder-problems-that-inherit-this-idea}
- **CSES — Exponentiation** (