Problem link ও উৎস
- **Original source:** LeetCode — Minimum Moves to Equal Array Elements II
- **Platform:** LeetCode —
(related: CSES Stick Lengths —
)
- **Topic:** Math-based programming fundamentals → Level 8: Greedy Math Tricks
- **Difficulty:** Medium
- **Pattern:** median target (সবাইকে median-এ আনলে মোট দূরত্ব সর্বনিম্ন)
- **Basic idea inherited from:** — (এই শাখার স্বাধীন গোড়া)
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
একটা integer array `nums` দেওয়া। এক "move"-এ তুমি যেকোনো একটা উপাদানকে 1 বাড়াতে বা 1 কমাতে পারো। লক্ষ্য — সব উপাদানকে **সমান** করা (সবাই একই মান হয়ে যাক)। প্রশ্ন: সবচেয়ে কম কত move-এ এটা করা যায়?
যেহেতু প্রতিটা উপাদানকে target `t`-তে আনতে `|nums[i] − t|` move লাগে, মোট move = `Σ |nums[i] − t|`। তাই আসল প্রশ্ন — কোন `t` বাছলে এই যোগফল সবচেয়ে ছোট হয়, আর তখন যোগফলটা কত?
উদাহরণ: `nums = [1, 2, 3]`। `t = 2` নিলে move = `|1−2| + |2−2| + |3−2|` = `1 + 0 + 1` = **2**। অন্য কোনো `t`-তে এর চেয়ে কম হয় না (যেমন `t = 1` হলে `0 + 1 + 2 = 3`)।
### Input ও output {#6-example-input-and-output}
```text
nums output median (target) কেন
-----------------------------------------------------------
[1, 2, 3] 2 2 |1-2|+0+|3-2|
[1, 10, 2, 9] 16 9 (বা 2) জোড়: মাঝের যেকোনো মান চলে
[1, 0, 0, 8, 6] 14 1 sorted [0,0,1,6,8], মাঝে 1
[5] 0 5 এক উপাদান, আগেই সমান
[2, 2, 2] 0 2 সবাই সমান
[1, 2, 3, 4] 4 2 বা 3 জোড়: [2,3]-এর যেকোনোটি
```
মূল edge case: **এক উপাদান বা সব সমান** → 0 move; **জোড় সংখ্যক উপাদান** → median হিসেবে মাঝের দুটোর মধ্যে যেকোনো মান (এমনকি তাদের মাঝের যেকোনো মানও) সমান সর্বনিম্ন খরচ দেয় — তাই sorted array-র `n // 2` index-এর মানটা নিলেই হয়।
### চেনা উদাহরণে বোঝা {#4-real-life-analogy}
ভাবো একটা সরলরেখা রাস্তায় কয়েকটা বাড়ি, আর তুমি একটা কমন মিটিং-পয়েন্ট (যেমন একটা পোস্ট বক্স) বসাবে — যাতে সব বাড়ির লোকের মোট হাঁটা সবচেয়ে কম হয়। কোথায় বসাবে?
প্রথম ধারণা হতে পারে "সবার গড় জায়গায়" (average)। কিন্তু একটু ভাবো — যদি বেশিরভাগ বাড়ি একদিকে জড়ো, আর একটা বাড়ি অনেক দূরে একা থাকে, তাহলে average সেই একা বাড়ির দিকে টেনে যায়, ফলে জড়ো-হওয়া বেশিরভাগ লোককে বেশি হাঁটতে হয়। আসল চালাক জায়গা — **মাঝের বাড়িটা (median)**। সেখানে বসালে যত লোক বাঁয়ে আর যত লোক ডানে সমান, তাই box-টা একটু সরালেই এক পক্ষের লাভ অন্য পক্ষের সমান-বা-বেশি ক্ষতিতে কাটা পড়ে — অর্থাৎ সরিয়ে আর লাভ নেই। median = ন্যায্যতম মিলনস্থল।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#3-which-basic-idea-does-this-inherit-from}
এটা greedy/math শাখার একটা **স্বাধীন গোড়া** (tracker-এ "inherited from: —")। তবে এর চিন্তার ধরনটা এই level-এর কেন্দ্রীয় সুর: **একটা লোভী আন্দাজ (median) করো, তারপর exchange/ভারসাম্য argument দিয়ে প্রমাণ করো কেন সেটা সেরা।**
110 (Integer Break)-এও আমরা একই ভঙ্গিতে "বড় টুকরো ভাঙলে লাভ" দেখিয়ে greedy প্রমাণ করেছিলাম; এখানে "target সরালে কখন লাভ" দেখিয়ে median প্রমাণ করছি। এই "সামান্য নাড়িয়ে দেখো লাভ-ক্ষতি" (exchange argument) যুক্তিই এই level-এর প্রায় সব greedy-র মেরুদণ্ড — তাই স্বাধীন হলেও 110-এর সাথে দর্শনে যমজ।
### ভেতরের অঙ্ক {#2-what-is-the-math-idea}
মূল গাণিতিক সত্য — **`Σ |nums[i] − t|` সর্বনিম্ন হয় যখন `t` = median (মধ্যমা)**। এটা "L1 দূরত্ব minimize করে median" নামে পরিচিত (তুলনায়: বর্গ-দূরত্ব `Σ (nums[i] − t)²` minimize করে mean/average — দুটো আলাদা!)।
কেন median? **ভারসাম্যের যুক্তি**: ধরো target `t`-এ তোমার বাঁ দিকে (ছোট) `L`টা সংখ্যা, ডান দিকে (বড়) `R`টা। `t`-কে এক ধাপ ডানে সরালে বাঁ দিকের `L`টা সংখ্যা থেকে দূরত্ব 1 করে **বাড়ে** (মোট +L), ডান দিকের `R`টা থেকে 1 করে **কমে** (মোট −R)। তাই নিট পরিবর্তন `L − R`। যতক্ষণ `R > L` (ডানে বেশি), ডানে সরালে লাভ; `L > R` হলে বাঁয়ে সরালে লাভ। ভারসাম্য (আর সরিয়ে লাভ নেই) ঠিক সেখানে যেখানে দুই পাশ সমান — অর্থাৎ **median**-এ। তাই median-ই optimal target, আর সেখানকার `Σ |nums[i] − median|`-ই উত্তর।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#7-brute-force-thinking}
সবচেয়ে সরল চিন্তা — সম্ভাব্য প্রতিটা target `t` (array-র সবচেয়ে ছোট থেকে সবচেয়ে বড় মান পর্যন্ত) ধরে মোট দূরত্ব হিসাব করো, সবচেয়ে ছোটটা রাখো:
```python
def min_moves_brute(nums):
if not nums:
return 0
lo, hi = min(nums), max(nums)
best = float('inf')
for t in range(lo, hi + 1):
cost = sum(abs(x - t) for x in nums)
best = min(best, cost)
return best
```
এটা সব সম্ভাব্য target পরীক্ষা করে (optimal target সবসময় min ও max-এর মধ্যেই থাকে), তাই নিশ্চিত ঠিক উত্তর — asserts-এ এটাই reference। ছোট রেঞ্জে চমৎকার।
### কোথায় বেশি কাজ হতে পারে {#8-why-brute-force-may-be-slow}
এই brute force-এর খরচ O((range) × n) — যেখানে range = `max − min`। মানগুলো বড় হলে (যেমন 10⁹) range বিশাল, আর প্রতিটা target-এ আবার পুরো array ঘুরে দূরত্ব — সব মিলিয়ে অসম্ভব ধীর।
```text
nums-এ মান 10^9 পর্যন্ত, n = 10^5 হলে:
brute : ~10^9 × 10^5 = 10^14 ধাপ (সম্পূর্ণ অসম্ভব)
median: sort O(n log n) + এক pass O(n) (দ্রুত)
```
মূল অপচয় — আমরা সব possible target ঘুরে দেখছি, যেখানে গণিত আগেই বলে দিয়েছে উত্তর ঠিক একটা জায়গায়: median। তাই range যত বড়ই হোক, শুধু median বের করে এক pass-এই উত্তর।
### আরও ভালোভাবে ভাবা {#9-better-thinking}
মূল insight — optimal target সবসময় **median**। তাই brute force-এর সব-target-খোঁজা বাদ; শুধু median বের করো, আর সেখানকার মোট দূরত্ব যোগ করো:
```python
def min_moves(nums):
if not nums:
return 0
s = sorted(nums)
median = s[len(s) // 2] # মধ্যমা (জোড় হলে মাঝের দুটোর একটি)
return sum(abs(x - median) for x in s)
```
sort করতে O(n log n), median-এ দূরত্ব যোগ করতে O(n)। median বের করার আরও দ্রুত উপায় আছে (quickselect, O(n)), কিন্তু sort পরিষ্কার ও যথেষ্ট।
### ভাবনার পরিবর্তন {#10-thinking-tweak}
আসল "আহা!" — **দূরত্ব (absolute difference) minimize করে median; বর্গ-দূরত্ব minimize করে average। দুটো গুলিও না!**
কেন median? "ভারসাম্য" দিয়ে ভাবো: target-কে এক ধাপ সরালে এক পাশের সব সংখ্যা থেকে দূরত্ব সমান বাড়ে, অন্য পাশের থেকে সমান কমে — তাই লাভ-ক্ষতি নির্ভর করে শুধু **কোন পাশে কতগুলো সংখ্যা** তার উপর, তাদের মান কত তাতে নয়। যতক্ষণ এক পাশে বেশি সংখ্যা, সেদিকে সরালে লাভ; ঠিক ভারসাম্যে (দুই পাশে সমান = median) থামো। "প্রতি ধাপের খরচ = দূরত্ব, সবাইকে এক বিন্দুতে আনো" দেখলেই median মাথায় আসুক — average নয়।
### ছবিতে বোঝা {#5-visual-explanation}
`nums = [1, 2, 9]` (sorted)। target সরালে মোট দূরত্ব কীভাবে বদলায় দেখি:
```text
number line: 1 2 9
| | |
t=1 : |1-1|+|2-1|+|9-1| = 0+1+8 = 9
t=2 : |1-2|+|2-2|+|9-2| = 1+0+7 = 8 <- median (মাঝের সংখ্যা) -> সর্বনিম্ন
t=5 : |1-5|+|2-5|+|9-5| = 4+3+4 = 11
t=9 : |1-9|+|2-9|+|9-9| = 8+7+0 = 15
median = 2 (3টা সংখ্যার মাঝেরটা), উত্তর = 8
```
ভারসাম্যের ছবি — t এক ধাপ সরালে বাঁ/ডানে কী ঘটে:
```text
বাঁয়ে L টা ডানে R টা
... [x][x][x] t [y][y][y][y] ...
<--- t ডানে সরালে:
বাঁ-এর L সংখ্যা থেকে +L (দূরত্ব বাড়ে)
ডান-এর R সংখ্যা থেকে -R (দূরত্ব কমে)
নিট = L - R। R>L হলে সরালে লাভ; সমান হলে (=median) থামো।
```
median-এ এসে বাঁ-ডান ভারসাম্য, তাই আর সরিয়ে লাভ নেই — সেটাই সর্বনিম্ন।
### ছোট input-এ ধাপে ধাপে {#11-step-by-step-dry-run}
`nums = [1, 0, 0, 8, 6]` ধরে median পথে চালাই:
1. শুরুর অবস্থা: array `[1, 0, 0, 8, 6]`, length 5।
2. sort: `s = [0, 0, 1, 6, 8]`।
3. median index = `len(s) // 2` = `5 // 2` = `2` → `s[2]` = **1**। তাই target = 1।
4. প্রতিটা থেকে দূরত্ব: `|0−1| + |0−1| + |1−1| + |6−1| + |8−1|` = `1 + 1 + 0 + 5 + 7`।
5. যোগফল = **14**।
মানে সবাইকে 1-এ আনতে 14 move লাগবে, আর এটাই সর্বনিম্ন — brute force-এর সাথে মিলে গেল। (যাচাই: target 0 নিলে `0+0+1+8+6 = 15`, target 6 নিলে `6+6+5+0+2 = 19` — দুটোই বেশি; median-ই জেতে।)
## কোড ও ব্যাখ্যা {#code}
### Python {#12-python-solution}
```python
def min_moves(nums):
"""সব উপাদান সমান করতে ন্যূনতম ±1 move (target = median)। O(n log n)।"""
if not nums:
return 0
s = sorted(nums)
median = s[len(s) // 2] # মধ্যমা — দূরত্ব-যোগফল এখানে সর্বনিম্ন
return sum(abs(x - median) for x in s)
def min_moves_brute(nums):
"""সব সম্ভাব্য target পরীক্ষা করে — reference।"""
if not nums:
return 0
lo, hi = min(nums), max(nums)
best = float('inf')
for t in range(lo, hi + 1):
best = min(best, sum(abs(x - t) for x in nums))
return best
# --- হাতে বাছা test ---
assert min_moves([1, 2, 3]) == 2
assert min_moves([1, 10, 2, 9]) == 16
assert min_moves([1, 0, 0, 8, 6]) == 14
assert min_moves([5]) == 0
assert min_moves([2, 2, 2]) == 0
assert min_moves([1, 2, 3, 4]) == 4
assert min_moves([]) == 0
# --- brute force-এর সাথে cross-check (random) ---
import random
random.seed(11)
for _ in range(3000):
n = random.randint(0, 8)
arr = [random.randint(-15, 15) for _ in range(n)]
assert min_moves(arr) == min_moves_brute(arr), (arr, min_moves(arr), min_moves_brute(arr))
print(min_moves([1, 0, 0, 8, 6])) # 14
print(min_moves([1, 2, 3])) # 2
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#13-line-by-line-explanation}
```text
if not nums: return 0
```
ফাঁকা array-তে কিছু সমান করার নেই — 0 move। (এই guard না থাকলে নিচে `s[len(s)//2]` খালি list-এ index error দিত।)
```text
s = sorted(nums)
```
median বের করতে আগে sort করি। sort করায় মাঝের উপাদানটাই median হয়ে যায় — খুঁজে বের করা সহজ।
```text
median = s[len(s) // 2]
```
মধ্যমা = sorted array-র মাঝের উপাদান। বিজোড় দৈর্ঘ্যে এটা ঠিক মাঝেরটা; জোড় দৈর্ঘ্যে এটা মাঝের দুটোর মধ্যে ডানেরটা — কিন্তু জোড়ে মাঝের যেকোনো মানই সমান সর্বনিম্ন দূরত্ব দেয়, তাই এটাই যথেষ্ট (আলাদা গড় নেওয়ার দরকার নেই)।
```text
return sum(abs(x - median) for x in s)
```
median-এ সবাইকে আনতে মোট move = প্রতিটার `|x − median|`-এর যোগফল। এটাই সর্বনিম্ন, কারণ median ভারসাম্য-বিন্দু।
cross-check অংশে 3000টা random array-তে median-পথ আর সব-target brute মিলিয়ে দেখা (negative মানসহ) — সব মিললে `সব test pass!`।
### Output মিলিয়ে দেখা {#14-output-walkthrough}
চালালে যা ছাপবে:
```text
14
2
সব test pass!
```
প্রথম লাইন: `[1, 0, 0, 8, 6]` → dry run-এ পাওয়া 14 (target median 1)। দ্বিতীয়: `[1, 2, 3]` → target 2, move `1+0+1 = 2`। তার আগের সব `assert` (হাতে বাছা + 3000টা random cross-check) চুপচাপ pass। সবশেষে `সব test pass!` — median সব কেসে সর্বনিম্ন দিয়েছে।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#15-time-complexity}
**O(n log n)** — মূল খরচ sort করা। তারপর median-এ দূরত্ব যোগ করা এক pass, O(n)। তাই সব মিলিয়ে O(n log n)। (চাইলে quickselect দিয়ে median O(n)-এ বের করে পুরোটা O(n) করা যায়, কিন্তু sort পরিষ্কার ও যথেষ্ট দ্রুত।)
### অতিরিক্ত জায়গা {#16-space-complexity}
**O(n)** — `sorted()` একটা নতুন list বানায়। চাইলে `nums.sort()` দিয়ে in-place করে O(1) বাড়তি স্মৃতিতে নামানো যায় (যদি input বদলানো allowed হয়)। মূল গণনায় বাড়তি কিছু লাগে না।
### যে ভুলগুলো এড়াতে হবে {#17-common-mistakes}
1. **average নেওয়া** — দূরত্ব minimize করে **median**, mean নয়। average নিলে outlier-এ ভুল উত্তর (যেমন `[1, 2, 9]`-এ average 4, কিন্তু সেরা target 2)।
2. **জোড় দৈর্ঘ্যে দুই median-এর গড় বের করা** — জোড়ে মাঝের যেকোনো মান (এমনকি `s[n//2]`) সমান সর্বনিম্ন দেয়; গড় বের করার দরকার নেই (আর integer move-এ গড় ভগ্নাংশ হলে ঝামেলা)।
3. **median-এর বদলে min বা max-এ আনা** — দুই প্রান্তে আনলে দূরত্ব সবচেয়ে বেশি; ঠিক উল্টো ভুল।
4. **negative সংখ্যা ভুলে যাওয়া** — `|x − t|` negative মানেও ঠিক কাজ করে; শুধু absolute নিতে ভুলো না।
5. **ফাঁকা array না সামলানো** — খালি list-এ `s[len(s)//2]` index error; গোড়ায় `return 0`।
## শেখা ও পরের অনুশীলন {#practice}
### এই ধারণার পরের অনুশীলন {#18-harder-problems-that-inherit-this-idea}
- **CSES — Stick Lengths** (