Problem link ও উৎস
- **Original source:** Classic CP technique (contribution / per-element counting)
- **Platform:** Classic CP technique —
- **Topic:** Math-based programming fundamentals → Level 5: Prefix, Difference, Contribution
- **Difficulty:** Medium
- **Pattern:** contribution technique (count subarrays containing each index)
- **Basic idea inherited from:** 045 — counting / combinatorics basics
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
একটা array `a` (দৈর্ঘ্য n) দেওয়া। প্রতিটা index `i`-এর জন্য বলতে হবে — **মোট কয়টা contiguous subarray-তে element `a[i]` আছে?**
মানে কোনো মান যোগ-টোগ নয় এখনই; শুধু গোনা: index `i`-কে ঢাকে এমন subarray-র সংখ্যা। যেমন `a = [1, 2, 3]`-এ index 1 (মান 2) আছে 4টা subarray-তে: `[2]`, `[1,2]`, `[2,3]`, `[1,2,3]`। এই গোনাটাই contribution technique-এর প্রথম ধাপ — পরের problem (076)-এ এই count দিয়ে আসল কাজ হবে।
### Input ও output {#6-example-input-and-output}
```text
a = [1, 2, 3], n = 3
count per index = [3, 4, 3] ((i+1)*(n-i))
a = [10], n = 1
count = [1] (একটাই subarray, একটাই element)
a = [5, 6, 7, 8], n = 4
count = [4, 6, 6, 4] (1·4, 2·3, 3·2, 4·1)
a = [1, 1], n = 2
count = [2, 2] (1·2, 2·1)
```
লক্ষ করো count সবসময় symmetric (আয়নার মতো) — প্রান্ত থেকে কেন্দ্রের দিকে বাড়ে, কারণ কেন্দ্রের element-এর দুই পাশে বেশি জায়গা। আর count আসল মান `a[i]`-এর উপর নির্ভর করে না, শুধু position-এর উপর।
### চেনা উদাহরণে বোঝা {#4-real-life-analogy}
ভাবো একটা লম্বা ট্রেনে n টা বগি, পরপর সাজানো (index 0 থেকে n-1)। একটা "টিকিট" মানে পরপর কয়েকটা বগির একটা টানা অংশ — শুরুর বগি থেকে শেষের বগি পর্যন্ত।
তুমি জানতে চাও: বগি নম্বর `i` মোট কয়টা টিকিটে পড়ে? টিকিটের শুরু হতে হবে বগি `i` বা তার বাঁয়ে — মানে 0 থেকে `i` পর্যন্ত, `(i+1)` রকম শুরু। আর শেষ হতে হবে বগি `i` বা তার ডানে — `i` থেকে `n-1` পর্যন্ত, `(n-i)` রকম শেষ।
শুরু আর শেষ আলাদাভাবে বাছাই, তাই মোট টিকিট = `(i+1) × (n-i)`। প্রতিটা বগির জন্য আলাদা করে গুনলে — মাঝের বগিগুলো বেশি টিকিটে পড়ে (বেশি option), প্রান্তের বগি কম।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#3-which-basic-idea-does-this-inherit-from}
মূলত **045 (counting / combinatorics basics)** থেকে — "স্বাধীন পছন্দ থাকলে গুণ করো" এই গুণনীতি। এখানে দুটো স্বাধীন পছন্দ: subarray-র বাঁ প্রান্ত আর ডান প্রান্ত।
prefix/difference থেকে এটা আলাদা চিন্তা — সেখানে "running total"; এখানে "কে কয়টায় আছে"। কিন্তু দুটোরই উদ্দেশ্য এক: O(n²) কাজকে O(n)-এ নামানো। contribution technique পুরো "sum over all subarrays" ঘরানার মাস্টার কী — আর তার ভিত্তি এই সহজ গোনা।
### ভেতরের অঙ্ক {#2-what-is-the-math-idea}
মূল idea হলো **per-element counting via independent choices** (স্বাধীন পছন্দের গুণফল)।
একটা subarray ঠিক হয় দুটো জিনিসে: শুরুর index `l` আর শেষের index `r`। index `i`-কে ঢাকতে হলে `l ≤ i ≤ r` হতে হবে। তাহলে:
```text
শুরু l বাছার option: 0, 1, ..., i → (i + 1) টা
শেষ r বাছার option: i, i+1, ..., n-1 → (n - i) টা
```
`l` আর `r` স্বাধীনভাবে বাছা যায়, তাই গুণ:
```text
index i-কে ঢাকা subarray-র সংখ্যা = (i + 1) * (n - i)
```
এটা combinatorics-এর সরল গুণনীতি (rule of product): দুটো স্বাধীন পছন্দ মিলে মোট সংখ্যা = পছন্দ১ × পছন্দ২।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#7-brute-force-thinking}
প্রতিটা index-এর জন্য সব subarray ঘুরে গুনি কোনগুলো ঢাকে:
```python
def count_brute(a):
n = len(a)
counts = [0] * n
for l in range(n):
for r in range(l, n): # প্রতিটা subarray (l..r)
for i in range(l, r + 1):
counts[i] += 1 # এই subarray যাদের ঢাকে, সবার count++
return counts
```
সরল, ঠিক উত্তর দেয় — প্রতিটা subarray ধরে তার ভেতরের সব index-এর count বাড়ায়।
### কোথায় বেশি কাজ হতে পারে {#8-why-brute-force-may-be-slow}
তিনটা nested loop! বাইরের দুটো subarray (n²/2 টা), ভেতরেরটা subarray-র দৈর্ঘ্য ধরে — মোট **O(n³)**। (এমনকি ভেতরের loop বাদ দিয়ে শুধু subarray গুনলেও O(n²)।)
```text
n = 1000 হলে:
brute force (O(n³)): ~10^9 operation — খুব ধীর
formula way (O(n)) : ~1000 operation — চোখের পলকে
```
অপচয়টা স্পষ্ট: একই index বারবার গোনা হচ্ছে নানা subarray-তে। অথচ একটা সহজ সূত্রেই গোনার সংখ্যা সরাসরি বেরিয়ে আসে।
### আরও ভালোভাবে ভাবা {#9-better-thinking}
মূল insight: index `i`-কে গুনতে subarray ঘুরো না — শুধু গণনা করো কয়ভাবে বাঁ প্রান্ত আর ডান প্রান্ত বাছা যায়। `(i+1)` রকম শুরু, `(n-i)` রকম শেষ, স্বাধীন তাই গুণ:
```python
def count_subarrays_with_index(a):
n = len(a)
return [(i + 1) * (n - i) for i in range(n)]
```
প্রতিটা index-এর জন্য একটা গুণ — মোট **O(n)**। O(n³) (বা O(n²)) থেকে নেমে এল এক সূত্রে।
### ভাবনার পরিবর্তন {#10-thinking-tweak}
আসল "আহা!" মুহূর্ত: **subarray গুনতে subarray ঘুরো না — প্রতিটা element-কে জিজ্ঞেস করো "তুমি কয়টায় আছ?"** দৃষ্টিভঙ্গি subarray থেকে element-এ সরালে গোনাটা দুটো স্বাধীন পছন্দের গুণফলে নেমে আসে।
আর সেই গুণফল মনে রাখার চাবি: `(i + 1) * (n - i)` — বাঁয়ে `i+1` রকম শুরু (index 0 থেকে i), ডানে `n-i` রকম শেষ (index i থেকে n-1)। মুখস্থ কোরো না, ছবি আঁকো — কোন প্রান্তে কতগুলো option। এই "প্রশ্ন উল্টে দাও" tweak-টাই contribution technique-এর প্রাণ, যা 076-077-এ আসল কাজে লাগবে।
### ছবিতে বোঝা {#5-visual-explanation}
`a = [1, 2, 3]`, n = 3। index 1 (মান 2)-কে কয়টা subarray ঢাকে?
```text
index: 0 1 2
a: [ 1 ] [ 2 ] [ 3 ]
↑
এই element কোথায় কোথায় আছে?
শুরু l বাছা (≤ 1): l = 0 বা l = 1 → 2 রকম (i + 1 = 1 + 1 = 2)
শেষ r বাছা (≥ 1): r = 1, 2 → 2 রকম (n - i = 3 - 1 = 2)
মোট = 2 × 2 = 4 টা subarray:
l=0,r=1: [1,2]
l=0,r=2: [1,2,3]
l=1,r=1: [2]
l=1,r=2: [2,3] ✓ চারটাই index 1 ঢাকে
```
প্রতিটা index-এর জন্য count:
```text
index i: 0 1 2
(i + 1): 1 2 3 ← বাঁয়ে শুরুর option
(n - i): 3 2 1 ← ডানে শেষের option
count = গুণ: 3 4 3 ← এই index কয়টা subarray-তে
মোট subarray = 3 + 4 + 3 = ... না! মোট subarray = n(n+1)/2 = 6।
(count-এর যোগফল ≠ subarray সংখ্যা; এটা "element-উপস্থিতি"-র যোগফল।)
```
মূল কথা: মাঝের index বেশি subarray-তে (বেশি option দুই পাশে), প্রান্তের কম। ছবিটা ধরো — বাঁয়ে পছন্দ × ডানে পছন্দ।
### ছোট input-এ ধাপে ধাপে {#11-step-by-step-dry-run}
`a = [5, 6, 7, 8]`, n = 4। প্রতিটা index-এর count:
| i | i + 1 (বাঁ option) | n - i (ডান option) | count = (i+1)*(n-i) |
| --- | --- | --- | --- |
| 0 | 1 | 4 | 1 × 4 = 4 |
| 1 | 2 | 3 | 2 × 3 = 6 |
| 2 | 3 | 2 | 3 × 2 = 6 |
| 3 | 4 | 1 | 4 × 1 = 4 |
ফল: `[4, 6, 6, 4]`। যাচাই index 1: subarray গুলো যেগুলো index 1 ঢাকে — শুরু {0,1} × শেষ {1,2,3} = 2×3 = 6টা ✓। symmetric pattern (4,6,6,4) চোখে পড়ছে।
## কোড ও ব্যাখ্যা {#code}
### Python {#12-python-solution}
```python
def count_subarrays_with_index(a):
"""প্রতিটা index i কয়টা subarray-তে আছে: (i+1)*(n-i)। O(n)।"""
n = len(a)
return [(i + 1) * (n - i) for i in range(n)]
def count_brute(a):
"""ধীর O(n^3) version — প্রতিটা subarray ধরে গোনা; মিলিয়ে দেখার জন্য।"""
n = len(a)
counts = [0] * n
for l in range(n):
for r in range(l, n):
for i in range(l, r + 1):
counts[i] += 1
return counts
# --- ছোট test গুলো (সব pass করা উচিত) ---
assert count_subarrays_with_index([1, 2, 3]) == [3, 4, 3]
assert count_subarrays_with_index([10]) == [1]
assert count_subarrays_with_index([5, 6, 7, 8]) == [4, 6, 6, 4]
assert count_subarrays_with_index([1, 1]) == [2, 2]
assert count_subarrays_with_index([]) == [] # খালি array
# count আসল মানের উপর নির্ভর করে না, শুধু length-এর উপর:
assert count_subarrays_with_index([99, -7, 0]) == count_subarrays_with_index([1, 2, 3])
# fast আর brute একই উত্তর কিনা (brute-force cross-check):
for length in range(0, 9):
arr = list(range(length)) # মান যাই হোক, count একই
assert count_subarrays_with_index(arr) == count_brute(arr)
# প্রতিটা count-এর যোগফল = সব subarray-র মোট দৈর্ঘ্য (আরেকটা সঙ্গতি-চেক):
def total_length_brute(a):
n = len(a); tot = 0
for l in range(n):
for r in range(l, n):
tot += (r - l + 1)
return tot
for length in range(0, 9):
arr = list(range(length))
assert sum(count_subarrays_with_index(arr)) == total_length_brute(arr)
print(count_subarrays_with_index([1, 2, 3])) # [3, 4, 3]
print(count_subarrays_with_index([5, 6, 7, 8])) # [4, 6, 6, 4]
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#13-line-by-line-explanation}
```text
n = len(a)
return [(i + 1) * (n - i) for i in range(n)]
```
পুরো সমাধান এক লাইনে। প্রতিটা index `i`-এর জন্য: `(i + 1)` = বাঁয়ে শুরু বাছার রকম (index 0 থেকে i), `(n - i)` = ডানে শেষ বাছার রকম (index i থেকে n-1)। স্বাধীন পছন্দ, তাই গুণ — সেটাই index `i`-কে ঢাকা subarray-র সংখ্যা।
```text
for l in range(n):
for r in range(l, n):
for i in range(l, r + 1):
counts[i] += 1
```
ধীর brute — প্রতিটা subarray `(l..r)` ধরে, তার ভেতরের সব index-এর count বাড়ায়। তিন স্তরের loop, শুধু সূত্র মিলিয়ে দেখার জন্য।
বাকি `assert` গুলো নির্দিষ্ট উদাহরণ + সব length-এ fast আর brute মিলিয়ে দেখছে (brute-force cross-check), আর দুটো সঙ্গতি-চেক: count আসল মান-নিরপেক্ষ, এবং count-এর যোগফল = সব subarray-র মোট দৈর্ঘ্য। সব মিললে `সব test pass!`।
### Output মিলিয়ে দেখা {#14-output-walkthrough}
`a = [1, 2, 3]`:
- i=0: `1 × 3 = 3`
- i=1: `2 × 2 = 4`
- i=2: `3 × 1 = 3`
- ফল `[3, 4, 3]` → প্রথম `print`
- `[5,6,7,8]` → `[4, 6, 6, 4]` → দ্বিতীয় `print`
- সব `assert` pass → `সব test pass!`
ছাপা output:
```text
[3, 4, 3]
[4, 6, 6, 4]
সব test pass!
```
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#15-time-complexity}
**O(n)** — প্রতিটা index-এর জন্য একটা গুণ, n টা index। brute force-এর O(n³) (বা subarray-শুধু-গুনলে O(n²)) থেকে বিশাল উন্নতি।
### অতিরিক্ত জায়গা {#16-space-complexity}
**O(n)** — n দৈর্ঘ্যের count array ফেরত দিচ্ছি। শুধু count চাইলে এটুকুই; প্রতিটা আলাদা ছাপলে O(1) extra-ও সম্ভব।
### যে ভুলগুলো এড়াতে হবে {#17-common-mistakes}
1. **`(i + 1) * (n - i)` আর `i * (n - i - 1)` গুলিয়ে ফেলা** — বাঁয়ে option `i+1` (index 0..i), ডানে `n-i` (index i..n-1)। ছবি আঁকো, মুখস্থ কোরো না।
2. **0-indexing vs 1-indexing** — এই সূত্র 0-indexed। 1-indexed হলে `i * (n - i + 1)` হয়; convention মিলিয়ে নাও।
3. **count-এর যোগফল = subarray সংখ্যা ভাবা** — না; count-এর যোগফল = সব subarray-র মোট দৈর্ঘ্য। subarray সংখ্যা আলাদা: `n(n+1)/2`।
4. **count আসল মানের উপর নির্ভর ভাবা** — count শুধু position-নির্ভর; `a[i]`-র মান এখানে অপ্রাসঙ্গিক (মান লাগবে 076-এ গুণ করার সময়)।
5. **প্রান্ত off-by-one** — index 0-এর বাঁয়ে শুরু মাত্র 1 রকম (নিজেই), index n-1-এর ডানে শেষ মাত্র 1 রকম; সূত্র এটা ঠিক দেয় কিনা প্রান্তে যাচাই করো।
## শেখা ও পরের অনুশীলন {#practice}
### এই ধারণার পরের অনুশীলন {#18-harder-problems-that-inherit-this-idea}
- **076 (Sum of All Subarrays)** — এই count-কে `a[i]` দিয়ে গুণ করে সব subarray-র sum-এর যোগফল (পরের ধাপ)।
- **078 (Pair Contribution Problems)** — element-এর বদলে pair ধরে একই "কে কয়টায় আছে" চিন্তা।
- **LeetCode — Sum of Subarray Minimums** (