Problem link ও উৎস
- **Original source:** Classic exercise (clock / wrap-around arithmetic word problems)
- **Platform:** Classic exercise — সব intro math আর programming course-এ থাকে
- **Topic:** Math-based programming fundamentals → Level 2: Modular Arithmetic
- **Difficulty:** Easy
- **Pattern:** clock model (wrap-around)
- **Basic idea inherited from:** 026 — Remainder Basics (clock model)
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
ঘড়ি বা চক্রাকার কিছু নিয়ে প্রশ্ন, যেখানে গুনতে গুনতে শেষে আবার শুরুতে ফিরে আসে:
- **12-ঘণ্টার ঘড়ি:** এখন `h`টা বাজে, `x` ঘণ্টা পরে কয়টা?
- **24-ঘণ্টা / সপ্তাহের দিন / সপ্তাহের চক্র:** এখন সোমবার, `d` দিন পরে কী বার?
- **পিছনে গোনা:** এখন 3টা, 5 ঘণ্টা **আগে** কয়টা ছিল?
সব ক্ষেত্রেই উত্তর modular arithmetic — শুধু ঠিক mod (12, 24, 7...) আর wrap-around সামলানো। মূল লক্ষ্য: ঘড়ির ছবিটা code-এ অনুবাদ করা শেখা।
### Input ও output {#6-example-input-and-output}
```text
12-ঘণ্টা ঘড়ি (1..12):
এখন পরে(+) -> কয়টা ব্যাখ্যা
-------------------------------------------------
9 8 -> 5 17 -> 5
9 4 -> 1 13 -> 1 (12 নয়, wrap)
12 1 -> 1 13 -> 1
3 -5 -> 10 পিছনে 5 -> 10
সপ্তাহের দিন (0=সোম .. 6=রবি):
আজ পরে(+) -> কী বার (index)
-------------------------------------------------
0 100 -> 2 100 % 7 = 2 -> বুধ
5 3 -> 1 8 % 7 = 1 -> মঙ্গল
24-ঘণ্টা:
এখন পরে(+) -> ঘণ্টা
-------------------------------------------------
22 5 -> 3 27 % 24 = 3
```
edge case: 12-ঘণ্টা ঘড়িতে উত্তর 12 হওয়া (0 নয়), পিছনে গোনায় negative wrap, আর বড় x (যেমন 100 ঘণ্টা) — সবই mod আপনিই সামলায়।
### চেনা উদাহরণে বোঝা {#4-real-life-analogy}
এটা নিজেই একটা analogy-base problem, তাই উল্টো দিক থেকে ভাবি — **একটা বৃত্তাকার সিঁড়ি**। তুমি কোনো ধাপে দাঁড়িয়ে, সিঁড়িতে মোট `m` ধাপ, শেষ ধাপের পরে আবার প্রথম ধাপ।
উপরে `x` ধাপ উঠলে কোথায়? এক এক ধাপ গোনার দরকার নেই — `(এখনকার ধাপ + x) % m`। নিচে নামলে বিয়োগ, আর শূন্যের নিচে গেলে নিচ থেকে আবার উপরে wrap (`+ m`)। ঘড়ি, সপ্তাহের দিন, মাসের তারিখ — সব এই বৃত্তাকার সিঁড়ি। mod হলো "চক্কর ভুলে শুধু কোন ধাপে দাঁড়ালে" তার হিসাব।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#3-which-basic-idea-does-this-inherit-from}
সরাসরি **026 — Remainder Basics** — clock model। 026-এ ঘড়িটা ছিল ধারণা; এখানে সেই ঘড়িকে বাস্তব word problem-এ প্রয়োগ। 026-এর negative-safe রূপ `((x % m) + m) % m` এখানে "পিছনে গোনা"-য় সরাসরি কাজে আসে।
আর 027 (modular addition/subtraction)-এর যোগ-বিয়োগ + negative সামলানো এখানে word problem-রূপে ফিরে আসে। মানে নতুন কোনো অস্ত্র নয় — 026/027-এর প্রয়োগ। এই note-টা তাই intuition পাকা করার, নতুন technique শেখার নয়।
### ভেতরের অঙ্ক {#2-what-is-the-math-idea}
মূল idea — **modular arithmetic = clock arithmetic** (026-এর ঘড়ি)। একটা m-ঘরের ঘড়িতে:
- সামনে যাওয়া: `(h + x) % m`
- পিছনে যাওয়া: `(h − x) % m`, কিন্তু negative হতে পারে — তাই `((h − x) % m + m) % m`
12-ঘণ্টার ঘড়ির একটা সূক্ষ্মতা: ঘর 1..12 (0 নয়), তাই হিসাবটা `((h + x − 1) % 12) + 1` — যাতে 12 ঠিক থাকে, 0 না হয়। 24-ঘণ্টা বা সপ্তাহের দিন (0..6) হলে সরাসরি `% m`।
মূলত: যেকোনো "ঘুরে শুরুতে ফেরা" গোনা = mod; দিক অনুযায়ী যোগ/বিয়োগ + negative-safe।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#7-brute-force-thinking}
সরল: এক এক ঘণ্টা/দিন করে কাঁটা ঘোরাও।
```python
def clock_brute(h, x, m):
h = h % m
if x >= 0:
for _ in range(x):
h = (h + 1) % m # এক ঘর সামনে
else:
for _ in range(-x):
h = (h - 1) % m # এক ঘর পিছনে
return h
```
ঠিক উত্তর দেয় — কাঁটা সত্যিই এক এক ঘর ঘোরে। সমস্যা: loop চলে `|x|` বার।
### কোথায় বেশি কাজ হতে পারে {#8-why-brute-force-may-be-slow}
loop ঘোরে `|x|` বার। `x = 10^18` ঘণ্টা হলে অসম্ভব। অথচ উত্তর তো একটা mod-এই পাওয়া যায়।
```text
x = 10^18 ঘণ্টা হলে:
brute (O(x)): 10^18 বার কাঁটা ঘোরাও -> অসম্ভব
mod (O(1)): (h + x) % m -> এক ধাপে
পার্থক্য: 10^18 vs 1
```
মূল শিক্ষা: চক্কর এক এক করে গোনার দরকার নেই — পুরো x-কে একবারে যোগ করে `% m`।
### আরও ভালোভাবে ভাবা {#9-better-thinking}
সরাসরি mod — দিক অনুযায়ী যোগ/বিয়োগ, negative-safe:
```python
def clock_24(h, x, m=24):
"""0-indexed ঘড়ি/চক্র (24-ঘণ্টা, সপ্তাহের দিন ইত্যাদি)।"""
return ((h + x) % m + m) % m # negative x-ও safe
def clock_12(h, x):
"""12-ঘণ্টা ঘড়ি: ঘর 1..12, 0 নয়।"""
return ((h + x - 1) % 12 + 12) % 12 + 1
```
`((... % m) + m) % m` রূপটা negative x সামলায় (পিছনে গোনা)। 12-ঘণ্টায় `−1 ... +1` কৌশল 12-কে 0 হতে দেয় না। দুটোই O(1) — x যত বড়/negative-ই হোক।
### ভাবনার পরিবর্তন {#10-thinking-tweak}
আসল "আহা!": **ঘড়ির যেকোনো "এতক্ষণ পরে/আগে" প্রশ্ন = `(now ± delta) % cycle` — চক্কর গোনার দরকার নেই, এক mod-এ উত্তর।** পুরো বড় delta-ও mod আপনিই ছোট করে দেয়।
দুটো সতর্কতা-tweak:
- **0-indexed না 1-indexed?** সপ্তাহের দিন/24-ঘণ্টা সাধারণত 0-indexed (সরাসরি `% m`); 12-ঘণ্টা ঘড়ি 1..12 (তাই `−1`/`+1` কৌশল)। কোন convention আগে ঠিক করো।
- **পিছনে গোনায় negative** — `((h − x) % m + m) % m` দিয়ে non-negative ঘরে আনো; এটাই 026-এর safe রূপ।
### ছবিতে বোঝা {#5-visual-explanation}
12-ঘণ্টার ঘড়ি, 9টা থেকে 8 ঘণ্টা পরে:
```text
12
11 1
10 2
9 ● 3 ● = এখন 9টা
8 4
7 6 5
9 + 8 = 17 -> 17 % 12 = 5 -> 5টা
(কাঁটা 12 পেরিয়ে আবার গুনল)
```
পিছনে গোনা — 3টা থেকে 5 ঘণ্টা আগে:
```text
3 - 5 = -2 -> negative! -> ((-2) % 12 + 12) % 12 = 10 -> 10টা
ঘড়িতে: 3 থেকে পিছনে 5 ঘর হাঁটলে -> 10টায় পৌঁছাই
12-ঘণ্টা ঘড়ির special form (1..12 রাখতে):
((h + x - 1) % 12) + 1 -> e.g. 9টা + 4 = ((9+4-1)%12)+1 = (12%12)+1 = 1টা
```
### ছোট input-এ ধাপে ধাপে {#11-step-by-step-dry-run}
`clock_12(9, 8)` (9টা থেকে 8 ঘণ্টা পরে):
```text
ভিতরের হিসাব ধাপে ধাপে:
h + x - 1 = 9 + 8 - 1 = 16
16 % 12 = 4
(4 + 12) % 12 = 4 (negative ছিল না, তাই অপরিবর্তিত)
4 + 1 = 5
উত্তর: 5টা ✓ (17 % 12 = 5 এর সাথে মিলল)
```
পিছনে গোনা `clock_12(3, -5)` (3টা থেকে 5 ঘণ্টা আগে):
| ধাপ | হিসাব | মান |
| --- | --- | --- |
| h + x − 1 | 3 + (−5) − 1 | −3 |
| % 12 | −3 % 12 | 9 (Python non-negative) |
| (+12) % 12 | (9 + 12) % 12 | 9 |
| + 1 | 9 + 1 | 10 |
উত্তর **10টা** ✓ (ঘড়িতে 3 থেকে পিছনে 5 ঘর = 10)।
## কোড ও ব্যাখ্যা {#code}
### Python {#12-python-solution}
```python
def clock_24(h, x, m=24):
"""0-indexed চক্র (24-ঘণ্টা, সপ্তাহের দিন 0..m-1)। x negative-ও safe।"""
return ((h + x) % m + m) % m
def clock_12(h, x):
"""12-ঘণ্টা ঘড়ি: ঘর 1..12 (0 নয়)। x negative-ও safe।"""
return ((h + x - 1) % 12 + 12) % 12 + 1
def day_after(today, days, week=7):
"""today (0=সোম..6=রবি) থেকে days দিন পরে কোন দিন।"""
return ((today + days) % week + week) % week
# --- 12-ঘণ্টা ঘড়ি test ---
assert clock_12(9, 8) == 5 # 17 -> 5
assert clock_12(9, 4) == 1 # 13 -> 1 (wrap)
assert clock_12(12, 1) == 1 # 13 -> 1
assert clock_12(3, -5) == 10 # পিছনে 5 -> 10
assert clock_12(12, 12) == 12 # পুরো এক চক্কর -> একই
assert clock_12(6, 0) == 6 # নড়েনি
# --- 24-ঘণ্টা / general 0-indexed test ---
assert clock_24(22, 5) == 3 # 27 % 24
assert clock_24(0, 100, 24) == 4 # 100 % 24 = 4
assert clock_24(5, -10, 24) == 19 # পিছনে wrap
assert clock_24(10, 10**18, 24) == (10 + 10**18) % 24 # বিশাল delta
# --- সপ্তাহের দিন test ---
assert day_after(0, 100) == 2 # সোম + 100 = বুধ (100%7=2)
assert day_after(5, 3) == 1 # 8 % 7 = 1
assert day_after(3, -5) == 5 # পিছনে: (3-5)%7 -> 5
# brute-এর সাথে মিল (ছোট x):
def clock_brute(h, x, m):
h %= m
step = 1 if x >= 0 else -1
for _ in range(abs(x)):
h = (h + step) % m
return h
for h in range(0, 24):
for x in range(-30, 30):
assert clock_24(h, x, 24) == clock_brute(h, x, 24)
print(clock_12(9, 8)) # 5
print(clock_24(22, 5)) # 3
print(day_after(0, 100)) # 2
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#13-line-by-line-explanation}
```text
def clock_24(h, x, m=24):
return ((h + x) % m + m) % m
```
0-indexed চক্রের সাধারণ রূপ: `h + x` (সামনে/পিছনে), তারপর `% m`। ভেতরের `% m`-এ negative এলে `+ m` করে আবার `% m` — non-negative ঘরে আসে (026-এর safe রূপ)।
```text
def clock_12(h, x):
return ((h + x - 1) % 12 + 12) % 12 + 1
```
12-ঘণ্টা ঘড়িতে ঘর 1..12। `−1` করে 0-indexed-এ নামাই, mod নিই (negative-safe সহ), তারপর `+ 1` করে আবার 1..12-এ ফিরি। এতে 12 ঠিক থাকে, ভুল করে 0 হয় না।
```text
def day_after(today, days, week=7):
return ((today + days) % week + week) % week
```
সপ্তাহের দিন 0..6-এর জন্য একই 0-indexed রূপ, m = 7।
```text
for h in range(0, 24):
for x in range(-30, 30):
assert clock_24(h, x, 24) == clock_brute(h, x, 24)
```
এই double loop সব শুরু-অবস্থান আর সামনে-পিছনে delta-তে slow brute (এক এক ঘর ঘোরা)-র সাথে মিলিয়ে দেখছে — negative সহ। বিশাল delta (10^18)-ও সরাসরি Python mod-এর সাথে মেলানো হয়েছে। সব ঠিক থাকলে শেষে `সব test pass!`।
### Output মিলিয়ে দেখা {#14-output-walkthrough}
চালালে যা ছাপবে:
```text
5
3
2
সব test pass!
```
প্রথম লাইন `clock_12(9, 8)` → 5 (9টা + 8 ঘণ্টা = 5টা)। দ্বিতীয় `clock_24(22, 5)` → 3 (22:00 + 5 = 03:00)। তৃতীয় `day_after(0, 100)` → 2 (সোম + 100 দিন = বুধ)। আগের সব `assert` (brute মিল + বিশাল delta সহ) চুপচাপ pass — তারপর `সব test pass!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#15-time-complexity}
**O(1)** — সব version-এ গুটিকয় যোগ আর mod; `x`/`days` যত বড় বা negative-ই হোক। brute O(|x|)-এর তুলনায় আকাশ-পাতাল (10^18 vs 1)।
### অতিরিক্ত জায়গা {#16-space-complexity}
**O(1)** — শুধু গুটিকয় variable; কোনো list/array লাগে না।
### যে ভুলগুলো এড়াতে হবে {#17-common-mistakes}
- **পিছনে গোনায় negative ভুলে যাওয়া** — `(h − x) % m` C++-এ negative দিতে পারে; `((h − x) % m + m) % m` দিয়ে non-negative করো (Python-এ `%` এমনিতেই non-negative, তবু অভ্যাস)।
- **12-ঘণ্টা ঘড়িতে 0 বনাম 12** — সরাসরি `% 12` দিলে 12টা-র জায়গায় 0 আসে; `((h + x − 1) % 12) + 1` কৌশল লাগে।
- **convention গুলিয়ে ফেলা** — কোনটা 0-indexed (দিন/24-ঘণ্টা), কোনটা 1-indexed (12-ঘণ্টা) — আগে ঠিক করো, নাহলে এক ঘর ভুল।
- **বড় x নিয়ে loop চালানো** — `x = 10^9` হলে এক এক ঘর গোনা TLE; সরাসরি mod।
- **mod ভুল বাছা** — সপ্তাহে 7, ঘণ্টায় 12/24, মাসের তারিখে... সঠিক cycle length বসাও।
- **AM/PM বা দিন-পরিবর্তন আলাদা চাইলে** — কয় দিন পেরোলো জানতে `(h + x) // m` (quotient) লাগে; শুধু কয়টা বাজে জানতে remainder।
## শেখা ও পরের অনুশীলন {#practice}
### এই ধারণার পরের অনুশীলন {#18-harder-problems-that-inherit-this-idea}
- **036 (Cyclic Remainder Pattern)** — ঘড়ির চক্রের ধারণাই power-এর cyclicity-তে গভীর হয়; যমজ idea।
- **Date/calendar problems (Zeller's congruence)** — কোন তারিখ কী বার বের করা; বড় আকারের clock arithmetic।
- **Josephus problem ও circular array rotation** (যেমন LeetCode — Rotate Array,