Problem link ও উৎস
- **Original source:** Classic technique (prefix mod + hash map)
- **Platform:** LeetCode Subarray Sums Divisible by K —
, CSES Subarray Divisibility —
- **Topic:** Math-based programming fundamentals → Level 5: Prefix, Difference, Contribution
- **Difficulty:** Medium
- **Pattern:** prefix sum mod K + hash map (same-remainder counting)
- **Basic idea inherited from:** 073 — Subarray Sum Equals K (এবং Level 2-এর 026 — modular arithmetic)
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
একটা সংখ্যার array `a` (negative-ও থাকতে পারে) আর একটা ধনাত্মক সংখ্যা `K` দেওয়া। তোমাকে গুনতে হবে — কতগুলো **contiguous subarray** আছে যাদের sum `K` দিয়ে নিঃশেষে ভাগ যায় (অর্থাৎ sum % K == 0)?
073-এর মতোই, শুধু শর্তটা "sum ঠিক K" থেকে বদলে "sum, K দিয়ে বিভাজ্য"। যেমন `a = [4, 5, 0, -2, -3, 1], K = 5` হলে উত্তর 7।
### Input ও output {#6-example-input-and-output}
```text
a K -> count
-----------------------------------------------
[4, 5, 0, -2, -3, 1] 5 -> 7 (LeetCode classic)
[5] 9 -> 0 একটাই element, বিভাজ্য নয়
[2, -2, 2, -4] 6 -> 2
[1, 2, 3, 4, 5] 3 -> 7
[-1, 2, 9] 2 -> 2
```
Edge case: **negative সংখ্যা** (`[4,5,0,-2,-3,1]`) — remainder normalize করতে হয় (Python এমনিতেই করে)। আর `0`-ও একটা element হতে পারে — তার remainder 0, hash map স্বাভাবিকভাবেই সামলায়।
### চেনা উদাহরণে বোঝা {#4-real-life-analogy}
ভাবো একটা বৃত্তাকার ঘড়ির ডায়াল যাতে `K` ঘর (যেমন 5 ঘরের ঘড়ি)। তুমি হাঁটছ আর প্রতিবার যোগফল অনুযায়ী কাঁটা ঘুরছে — কিন্তু `K` ঘরের পর আবার শুরুতে ফিরে আসছে (mod K)।
তুমি জানতে চাও — কোন কোন অংশে হাঁটার পর কাঁটা ঠিক **একই জায়গায় ফিরে এসেছে**? কারণ কাঁটা একই জায়গায় ফিরলে মানে মাঝের হাঁটাটা ঠিক `K`-এর গুণিতক — পুরো পাক!
তাই তুমি লিখে রাখো প্রতিটা ঘর-অবস্থানে (remainder) কতবার কাঁটা ছিল। একই অবস্থানে দুবার থাকা মানেই একটা বিভাজ্য অংশ। নোটবুকে (hash map) প্রতি অবস্থানের count রাখো, প্রতিবার "এই অবস্থানে আগে কতবার ছিলাম" যোগ করো।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#3-which-basic-idea-does-this-inherit-from}
মূলত **073 (Subarray Sum Equals K)** থেকে — হুবহু একই hash map কাঠামো। আর **Level 2-এর 026 (modular arithmetic)** থেকে remainder-এর ধর্ম।
073-এ key ছিল prefix sum-এর মান, খুঁজতাম `P - K`। এখানে key হলো prefix sum-এর **remainder** (`P % K`), আর খুঁজি **একই remainder**। কাঠামো প্রায় copy — শুধু "`P-K` কতবার" এর জায়গায় "`P % K` কতবার", আর `seen[0] = 1` একই কারণে থাকে। এই কারণেই 073 আগে শেখা দরকার — 074 তার পোশাক-বদল মাত্র।
### ভেতরের অঙ্ক {#2-what-is-the-math-idea}
মূল idea হলো **prefix sum mod K + একই remainder-এর জোড়া গোনা**।
subarray `(l..r)`-এর sum = `P[r] - P[l-1]`। এটা K দিয়ে বিভাজ্য মানে:
```text
(P[r] - P[l-1]) % K == 0 ⟺ P[r] % K == P[l-1] % K
```
মানে: **একই remainder-ওয়ালা দুটো prefix = একটা valid subarray।** তাই প্রতিটা remainder কতবার এসেছে গোনো; কোনো remainder যদি `c` বার আসে, সেগুলো থেকে `c·(c-1)/2` টা জোড়া বানানো যায় (অথবা চলার পথে প্রতিবার আগের count যোগ করলেই হয়)। গোনার যন্ত্র সেই hash map। Level 2-এর mod-চিন্তা (একই remainder = পার্থক্য বিভাজ্য) এখানে সরাসরি ফসল।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#7-brute-force-thinking}
সব `(l, r)` জোড়ার subarray-র sum বের করে `% K == 0` চেক:
```python
def count_div_k_brute(a, K):
n = len(a)
count = 0
for l in range(n):
s = 0
for r in range(l, n):
s += a[r]
if s % K == 0:
count += 1
return count
```
সরল, ঠিক উত্তর — প্রতিটা শুরু `l`-এর জন্য `r` বাড়িয়ে running sum, বিভাজ্য হলে count বাড়ায়।
### কোথায় বেশি কাজ হতে পারে {#8-why-brute-force-may-be-slow}
দুটো nested loop, প্রায় `n²/2` subarray — **O(n²)**।
```text
n = 30000 হলে:
brute force: ~4.5 × 10^8 operation (O(n²)) — TLE
hash way : ~30000 operation (এক pass, O(n))
```
073-এর মতোই অপচয়: প্রতিটা `l`-এর জন্য আবার ডান দিকে হাঁটা। অথচ remainder-এর frequency রাখলে "কতবার আগে একই remainder এসেছে" সরাসরি জানা যায়।
### আরও ভালোভাবে ভাবা {#9-better-thinking}
মূল insight: `(P[r] - P[l-1]) % K == 0` মানে `P[r] % K == P[l-1] % K`। তাই প্রতিটা remainder-এর frequency hash map-এ রাখি; প্রতি r-এ "আমার remainder আগে কতবার এসেছে" যোগ করি:
```python
def count_div_k(a, K):
from collections import defaultdict
seen = defaultdict(int)
seen[0] = 1 # খালি prefix (remainder 0) — শুরু থেকে বিভাজ্য subarray-র জন্য
P = 0
count = 0
for x in a:
P = (P + x) % K # remainder, Python-এ negative-ও [0, K)
count += seen[P] # একই remainder আগে যতবার = তত valid subarray
seen[P] += 1
return count
```
এক pass, প্রতি step O(1) — মোট **O(n)**। 073-এর প্রায় হুবহু code, শুধু key = `P % K`, আর খুঁজি একই remainder।
### ভাবনার পরিবর্তন {#10-thinking-tweak}
আসল "আহা!" মুহূর্ত: **বিভাজ্যতা = একই remainder।** sum বিভাজ্য কিনা সরাসরি না দেখে, দুটো prefix-এর remainder মেলানো — `P[r] % K == P[l-1] % K`। এটাই Level 2-এর "একই remainder মানে পার্থক্য বিভাজ্য" ধর্মের সরাসরি প্রয়োগ।
দ্বিতীয় tweak (ভাষা-নির্ভর ফাঁদ): **negative-এ remainder normalize করো।** Python-এ `(P + x) % K` এমনিতেই `[0, K)`-তে থাকে (সুবিধা!), কিন্তু C++/Java-তে negative আসে — তখন `((P % K) + K) % K` লাগে। এই অভ্যাসটা না থাকলে অন্য ভাষায় চুপচাপ ভুল answer।
### ছবিতে বোঝা {#5-visual-explanation}
`a = [2, -2, 2, -4], K = 6`। running prefix-এর remainder `P % K`, hash map `seen` (শুরুতে `{0: 1}`)। Python-এ `%` সবসময় `[0, K)`-তে remainder দেয়, negative-এও:
```text
শুরু: seen = {0: 1}, P = 0, count = 0
x = 2: P = (0 + 2) % 6 = 2
এই remainder আগে? seen[2] = 0 → count += 0। seen = {0:1, 2:1}
x = -2: P = (2 + (-2)) % 6 = 0
এই remainder আগে? seen[0] = 1 → count += 1 = 1। seen = {0:2, 2:1}
(remainder 0 আবার এল → শুরু থেকে এ পর্যন্ত sum বিভাজ্য: 2-2=0 ✓)
x = 2: P = (0 + 2) % 6 = 2
seen[2] = 1 → count += 1 = 2। seen = {0:2, 2:2}
(remainder 2 আবার → মাঝের অংশ -2+2=0 বিভাজ্য ✓)
x = -4: P = (2 + (-4)) % 6 = (-2) % 6 = 4 ← Python: negative-ও [0,6)-তে
seen[4] = 0 → count += 0 = 2। seen = {0:2, 2:2, 4:1}
উত্তর: count = 2
```
মূল কথা: একই remainder-এ ফিরে আসা = বিভাজ্য subarray। `(-2) % 6 = 4` — Python নিজেই normalize করে, কিন্তু C++/Java-তে এটা −2 আসত, তাই সেখানে `((P % K) + K) % K` লাগত। এই অভ্যাসটা মনে রাখো।
### ছোট input-এ ধাপে ধাপে {#11-step-by-step-dry-run}
`a = [-1, 2, 9], K = 2`। শুরুতে `seen = {0: 1}`, `P = 0`, `count = 0`:
| x | P = (P+x) % K | seen[P] (যোগ) | count | seen আপডেট |
| --- | --- | --- | --- | --- |
| -1 | (0-1) % 2 = 1 | 0 | 0 | {0:1, 1:1} |
| 2 | (1+2) % 2 = 1 | 1 | 1 | {0:1, 1:2} |
| 9 | (1+9) % 2 = 0 | 1 | 2 | {0:2, 1:2} |
শেষ অবস্থা: `count = 2`। দুটো বিভাজ্য subarray: `[2]` (sum 2 — index 0 আর index 1-এ remainder একই 1, তাই মাঝের `[2]` বিভাজ্য) আর `[-1, 2, 9]` (sum 10 — index 2-এ remainder 0 আবার এল, খালি prefix-এর সাথে মিলে পুরো array বিভাজ্য)। brute force-ও 2 দেয় ✓। (`(0-1) % 2 = 1` — Python নিজেই normalize করে, C++-এ −1 আসত।)
## কোড ও ব্যাখ্যা {#code}
### Python {#12-python-solution}
```python
from collections import defaultdict
def count_div_k(a, K):
"""sum K দিয়ে বিভাজ্য এমন contiguous subarray-র সংখ্যা; prefix mod + hash map, O(n)।"""
seen = defaultdict(int)
seen[0] = 1 # খালি prefix, remainder 0
P = 0
count = 0
for x in a:
P = (P + x) % K # Python: negative-ও [0, K)-তে normalize হয়
count += seen[P] # একই remainder আগে যতবার = তত নতুন subarray
seen[P] += 1
return count
def count_div_k_brute(a, K):
"""ধীর O(n^2) version — মিলিয়ে দেখার জন্য।"""
n = len(a)
count = 0
for l in range(n):
s = 0
for r in range(l, n):
s += a[r]
if s % K == 0:
count += 1
return count
# --- ছোট test গুলো (সব pass করা উচিত) ---
assert count_div_k([4, 5, 0, -2, -3, 1], 5) == 7 # LeetCode classic
assert count_div_k([5], 9) == 0
assert count_div_k([2, -2, 2, -4], 6) == 2
assert count_div_k([1, 2, 3, 4, 5], 3) == 7
assert count_div_k([-1, 2, 9], 2) == 2
# fast আর brute একই উত্তর কিনা (random brute-force cross-check):
import random
random.seed(19)
for _ in range(500):
arr = [random.randint(-5, 5) for _ in range(random.randint(0, 10))]
K = random.randint(1, 7)
assert count_div_k(arr, K) == count_div_k_brute(arr, K)
print(count_div_k([4, 5, 0, -2, -3, 1], 5)) # 7
print(count_div_k([1, 2, 3, 4, 5], 3)) # 7
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#13-line-by-line-explanation}
```text
seen = defaultdict(int)
seen[0] = 1
```
hash map (key = remainder, value = কতবার)। `seen[0] = 1` মানে "খালি prefix-এর remainder 0 একবার দেখেছি" — শুরু থেকে বিভাজ্য subarray গোনার জন্য।
```text
P = (P + x) % K
```
running prefix-এর remainder। Python-এ `%` সবসময় `[0, K)` দেয়, তাই negative `x`-এও remainder ঠিক থাকে — আলাদা normalize লাগে না (অন্য ভাষায় লাগত)।
```text
count += seen[P]
seen[P] += 1
```
এই remainder আগে যতবার এসেছে (`seen[P]`), ততগুলো নতুন বিভাজ্য subarray এখানে শেষ হচ্ছে — যোগ করলাম। তারপর নিজের remainder জমালাম। ক্রম: আগে খোঁজো, পরে লেখো।
বাকি `assert` গুলো নির্দিষ্ট উদাহরণ + random array-তে fast আর brute মিলিয়ে দেখছে (brute-force cross-check)। সব মিললে `সব test pass!`।
### Output মিলিয়ে দেখা {#14-output-walkthrough}
`a = [4, 5, 0, -2, -3, 1], K = 5`:
- remainder চলতে চলতে একই remainder বারবার ফিরে আসে; প্রতিবার আগের count যোগ হয়
- মোট হিসাবে `count = 7` → প্রথম `print` ছাপে `7`
- `count_div_k([1,2,3,4,5], 3)` → 7 → দ্বিতীয় `print` ছাপে `7`
- সব `assert` pass → `সব test pass!`
ছাপা output:
```text
7
7
সব test pass!
```
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#15-time-complexity}
**O(n)** — array-র উপর এক pass, প্রতি element-এ একটা hash lookup + insert (গড়ে O(1))। brute force-এর O(n²) থেকে বিশাল উন্নতি।
### অতিরিক্ত জায়গা {#16-space-complexity}
**O(K)** — hash map-এ remainder মাত্র K রকম (0 থেকে K-1), তাই entry সর্বোচ্চ K। 073-এর O(n)-এর চেয়েও কম, কারণ এখানে key বদ্ধ পরিসরে।
### যে ভুলগুলো এড়াতে হবে {#17-common-mistakes}
1. **negative remainder normalize না করা** — Python সামলায়, কিন্তু C++/Java-তে `-2 % 5 = -2`; তখন `((P % K) + K) % K` লাগে, নইলে key ভুল।
2. **`seen[0] = 1` ভুলে যাওয়া** — শুরু থেকে বিভাজ্য subarray গোনা হয় না (073-এর মতোই #1 bug)।
3. **key হিসেবে raw prefix sum রাখা (remainder নয়)** — তখন divisibility ধরা পড়ে না; key অবশ্যই `P % K`।
4. **খোঁজা-লেখার ক্রম উল্টানো** — আগে `count += seen[P]`, পরে `seen[P] += 1`; উল্টালে নিজের remainder নিজেকে গুনে বেশি আসে।
5. **`K = 0` ধরে নেওয়া** — divisibility-তে K ধনাত্মক হতে হয়; `% 0` error। প্রশ্নে K ≥ 1 ধরো।
## শেখা ও পরের অনুশীলন {#practice}
### এই ধারণার পরের অনুশীলন {#18-harder-problems-that-inherit-this-idea}
- **LeetCode — Subarray Sums Divisible by K** (