Problem link ও উৎস
- **Original source:** Classic prefix-mod + hash map exercise
- **Platform:** LeetCode —
- **Topic:** prefix sum + hash map (mod)
- **Difficulty:** Medium
- **Pattern:** prefix sum + hash map (mod)
- **Basic idea inherited from:** Subarray Sum Equals K — prefix-এর বদলে remainder জমা রাখো
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
একটা অঋণাত্মক সংখ্যার array `nums` আর একটা সংখ্যা `k` দেওয়া আছে। বলতে হবে: এমন কোনো **contiguous subarray** আছে কি, যার দৈর্ঘ্য অন্তত 2 আর যোগফল `k`-এর একটা গুণিতক (অর্থাৎ `0, k, 2k, 3k, ...`)? উত্তর `True`/`False`।
```text
nums = [23, 2, 4, 6, 7], k = 6
[2, 4]-এর যোগ 6 = 6 × 1 → হ্যাঁ
উত্তর: True
```
### Input ও output {#8-example-input-and-output}
```text
Input : [23, 2, 4, 6, 7], k = 6 Output: True ([2,4] = 6)
Input : [23, 2, 6, 4, 7], k = 6 Output: True (পুরোটা 42 = 6×7)
Input : [23, 2, 6, 4, 7], k = 13 Output: False
Edge : [0, 0], k = 1 Output: True ([0,0] = 0 = 0×1)
Edge : [1, 0], k = 2 Output: False (length-2 যোগ 1, গুণিতক নয়)
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
ভাবো একটা গোল ঘড়ির ডায়াল, ঘর সংখ্যা `k`। তুমি হাঁটছ আর প্রতিটা ধাপে কাঁটা কিছু ঘর এগোচ্ছে। যখনই কাঁটা **আগের কোনো ঘরে ফিরে আসে**, বোঝো এর মাঝে তুমি পূর্ণ পাক (k-এর গুণিতক) হেঁটেছ। প্রথমবার কোন ঘরে ছিলে তা মনে রাখলে বুঝতে পারো ফিরে আসতে অন্তত দুই ধাপ লেগেছে কি না।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#2-which-basic-idea-does-this-inherit-from}
এটা সরাসরি **Subarray Sum Equals K** (#13)-এর ভাই। সেখানে আমরা prefix value জমা রাখতাম; এখানে শুধু একটা মোচড় — prefix-এর বদলে **prefix % k** (remainder) জমা রাখি। ভিত্তি একই prefix-sum + hash map (Pattern 5), নতুন উপাদান modular arithmetic।
### ভেতরের যুক্তি {#3-what-is-the-hidden-math-or-logic}
মূল সংখ্যাতত্ত্ব: যদি দুটো prefix-এর `k` দিয়ে ভাগশেষ (remainder) এক হয়, তাহলে তাদের **বিয়োগফল `k`-এর গুণিতক**। কারণ `prefix[j] ≡ prefix[i] (mod k)` মানে `prefix[j] - prefix[i] ≡ 0 (mod k)`, আর সেই বিয়োগফলই হলো `(i, j]` subarray-র যোগফল। তাই "k-এর গুণিতক যোগফল আছে?" প্রশ্ন বদলে যায় "একই remainder কি আগে দেখেছি?" প্রশ্নে।
### কী দিয়ে তথ্য রাখব {#4-which-data-structure-is-needed}
একটা **hash map** (`remainder → সেই remainder প্রথম যে index-এ দেখা`)। count নয়, আমরা **প্রথম index** রাখি, কারণ দৈর্ঘ্য অন্তত 2 হতে হবে — বর্তমান index থেকে সেই প্রথম দেখা index-এর দূরত্ব মাপতে হবে।
### এটি কেন উপযুক্ত {#5-why-this-data-structure-fits}
আমরা প্রতিটা index-এ জিজ্ঞেস করি "এই remainder কি আগে দেখেছি, আর দূরত্ব ≥ 2?" hash map এই lookup O(1)-এ দেয়। আর প্রথম-দেখা index রাখলে দূরত্ব সবচেয়ে বড় হয়, তাই length ≥ 2 শর্ত মেলার সম্ভাবনাও সর্বোচ্চ থাকে। তাই একই remainder পরে আবার এলে map **overwrite করি না**।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
প্রথম সরল চিন্তা: দৈর্ঘ্য ≥ 2 প্রতিটা subarray ধরে যোগফল বের করো, দেখো `k`-এর গুণিতক কি না।
```text
প্রতিটা শুরু i-র জন্য:
running = nums[i]
প্রতিটা শেষ j > i-র জন্য:
running += nums[j]
running % k == 0 হলে return True
return False
```
### কোথায় বেশি কাজ হচ্ছে {#10-why-brute-force-is-slow}
দুটো nested loop মানে **O(n^2)**। আবারও সেই অপচয়: প্রতিটা শুরু-বিন্দুর জন্য বারবার একই অঞ্চলের যোগফল নতুন করে গোনা। অথচ remainder-এর পুনরাবৃত্তি একবার hash map-এ রাখলেই "k-এর গুণিতক যোগফল আছে?" এক pass-এ বলা যায়।
### যে বিষয়টি খেয়াল করতে হবে {#11-key-observation}
মূল observation: **k-এর গুণিতক যোগফল ⇔ দুই প্রান্তের prefix-এর remainder সমান।** তাই আসল subarray যোগফল হিসেব করারও দরকার নেই — শুধু running prefix-এর remainder চিনে রাখলেই হয়, আর "একই remainder আগে দেখেছি কি (≥ 2 দূরে)?" — এটাই উত্তর।
### আরও কম কাজে সমাধান {#12-optimized-intuition}
`seen = {0: -1}` দিয়ে শুরু করো (index -1 ধরে নিলে শুরু থেকে শুরু হওয়া subarray-ও দৈর্ঘ্য সঠিক পায়)। running `prefix` রাখো, প্রতিবার `r = prefix % k`। `r` আগে দেখা থাকলে আর দূরত্ব ≥ 2 হলে `True`; আগে না দেখা থাকলে **প্রথমবারের index লিখে রাখো** (পরে overwrite নয়)। শেষ পর্যন্ত না মিললে `False`। **O(n)**।
### ভাবনার পরিবর্তন {#13-thinking-tweak}
**মোচড়:** *যখন প্রশ্ন "গুণিতক/divisible", তখন prefix-এর জায়গায় prefix % k জমাও — সমান remainder মানেই গুণিতক ব্যবধান।* Subarray Sum Equals K-এর hash map চালটাই, শুধু key হিসেবে value নয়, value-র remainder। ছোট মোচড়, কিন্তু পুরো divisibility-পরিবার এতেই খোলে।
### ছবিতে বোঝা {#7-visual-explanation}
`nums = [23, 2, 4, 6, 7]`, `k = 6`। `seen` রাখে `remainder → প্রথম index`; শুরুতে `{0: -1}`:
```text
শুরু: prefix=0, seen={0:-1}
i=0 x=23: prefix=23, r=23%6=5, নতুন → seen={0:-1, 5:0}
i=1 x=2 : prefix=25, r=25%6=1, নতুন → seen={0:-1, 5:0, 1:1}
i=2 x=4 : prefix=29, r=29%6=5, আগে index 0! দূরত্ব 2-0=2 ≥ 2 → True
```
`r=5` আগে index 0-এ দেখা, এখন index 2 — মাঝের `[2,4]` যোগফল 6, যা 6-এর গুণিতক।
### ছোট input-এ ধাপে ধাপে {#14-step-by-step-dry-run}
Input `nums = [23, 2, 6, 4, 7]`, `k = 6`:
1. শুরু: `prefix = 0`, `seen = {0: -1}`।
2. `i=0, x=23`: `prefix=23`, `r=5`, নতুন → `seen={0:-1, 5:0}`।
3. `i=1, x=2`: `prefix=25`, `r=1`, নতুন → `seen={0:-1, 5:0, 1:1}`।
4. `i=2, x=6`: `prefix=31`, `r=1`, আগে index 1, দূরত্ব `2-1=1 < 2` → না (এবং overwrite নয়)।
5. `i=3, x=4`: `prefix=35`, `r=5`, আগে index 0, দূরত্ব `3-0=3 ≥ 2` → `True`।
## কোড ও ব্যাখ্যা {#code}
### Python {#15-python-solution}
```python
def check_subarray_sum(nums, k):
seen = {0: -1} # remainder -> প্রথম যেখানে দেখা
prefix = 0
for i, x in enumerate(nums):
prefix += x
r = prefix % k # mod দিয়ে partner খুঁজি
if r in seen:
if i - seen[r] >= 2: # length >= 2 চাই
return True
else:
seen[r] = i # শুধু প্রথমবার লিখি
return False
# ---- tests ----
assert check_subarray_sum([23, 2, 4, 6, 7], 6) == True
assert check_subarray_sum([23, 2, 6, 4, 7], 6) == True
assert check_subarray_sum([23, 2, 6, 4, 7], 13) == False
assert check_subarray_sum([0, 0], 1) == True
assert check_subarray_sum([1, 0], 2) == False
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#16-line-by-line-code-explanation}
- `seen = {0: -1}` — খালি prefix-এর remainder 0, index -1 ধরে, যাতে শুরু থেকে subarray-ও দৈর্ঘ্য ঠিক পায়।
- `for i, x in enumerate(nums)` — index ও value দুটোই লাগে (দূরত্ব মাপতে index)।
- `prefix += x` — running যোগফল।
- `r = prefix % k` — এই বিন্দুর remainder।
- `if r in seen: if i - seen[r] >= 2: return True` — একই remainder আগে দেখা, আর যথেষ্ট দূরে → গুণিতক subarray পেলাম।
- `else: seen[r] = i` — নতুন remainder হলে শুধু **প্রথম** index রাখি (দূরত্ব সর্বোচ্চ রাখতে overwrite করি না)।
### Output মিলিয়ে দেখা {#17-output-walkthrough}
`[23,2,4,6,7]` k=6-এ remainder 5 আবার আসে index 2-এ (আগে 0), দূরত্ব 2 → `True`। `[23,2,6,4,7]` k=6-এ remainder 5 আবার আসে index 3-এ (আগে 0), দূরত্ব 3 → `True`। একই array k=13-এ কোনো remainder ≥ 2 দূরত্বে পুনরাবৃত্তি হয় না → `False`। `[0,0]` k=1-এ remainder 0 index 1-এ (আগে -1), দূরত্ব 2 → `True`। শেষে print: `সব test pass!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#18-time-complexity}
**O(n)** — array-র উপর এক pass, প্রতি element-এ একটা mod আর hash map operation, সবই গড়ে O(1)।
### অতিরিক্ত জায়গা {#19-space-complexity}
**O(min(n, k))** — map-এ আলাদা remainder জমে, যা k-টার বেশি হতে পারে না (এবং n-এর বেশিও নয়)।
### যে ভুলগুলো এড়াতে হবে {#20-common-mistakes}
- count রেখে ফেলা (Subarray Sum Equals K-এর মতো) — এখানে দরকার **প্রথম index**, যাতে length ≥ 2 যাচাই হয়।
- একই remainder এলে index overwrite করা — তাতে দূরত্ব ছোট হয়ে valid উত্তর মিস হতে পারে; শুধু প্রথমবার লেখো।
- length ≥ 2 শর্ত ভুলে যাওয়া — তখন একক element-ও (বা শূন্য-দৈর্ঘ্য) ভুলভাবে True দেবে।
- `seen = {0: -1}` initialization বাদ দেওয়া — শুরু থেকে শুরু হওয়া গুণিতক subarray মিস হবে।
## শেখা ও পরের অনুশীলন {#practice}
### ভিত্তির সঙ্গে সম্পর্ক {#21-which-basic-problem-this-inherits-from}
ভিত্তি: Subarray Sum Equals K (#13)-এর prefix-sum + hash map, যা নিজে Two Sum + math fundamentals-এর prefix idea-র সংকর। নতুন উপাদান modular arithmetic — key হিসেবে `prefix % k`। সম্পূর্ণ চাল [../patterns.md](../patterns.md)-র Pattern 5-এ।
### পরের অনুশীলন {#22-similar-harder-problems}
- Subarray Sum Equals K —