111 — Make Array Equal with Minimum Moves¶

এই problem-টা একটা চমৎকার "কম জানা সত্য" শেখায়: সব সংখ্যাকে এক জায়গায় টেনে আনতে গেলে — যদি প্রতি ধাপের খরচ দূরত্ব হয় — সেরা গন্তব্য হলো median, average নয়! অনেকে প্রথমে average ভাবে আর ভুল করে। কেন median, তার একটা সুন্দর "ভারসাম্য" যুক্তি আছে, আর সেটাই এই note-এর প্রাণ। (এই level-এ মনে রেখো — greedy কেন কাজ করে, সেই প্রমাণটাই আসল।)

Source¶

Original source: LeetCode — Minimum Moves to Equal Array Elements II
Platform: LeetCode — https://leetcode.com/problems/minimum-moves-to-equal-array-elements-ii/ (related: CSES Stick Lengths — https://cses.fi/problemset/task/1074)
Topic: Math-based programming fundamentals → Level 8: Greedy Math Tricks
Difficulty: Medium
Pattern: median target (সবাইকে median-এ আনলে মোট দূরত্ব সর্বনিম্ন)
Basic idea inherited from: — (এই শাখার স্বাধীন গোড়া)

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)।

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|-ই উত্তর।

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-এর সাথে দর্শনে যমজ।

4. Real-life analogy¶

ভাবো একটা সরলরেখা রাস্তায় কয়েকটা বাড়ি, আর তুমি একটা কমন মিটিং-পয়েন্ট (যেমন একটা পোস্ট বক্স) বসাবে — যাতে সব বাড়ির লোকের মোট হাঁটা সবচেয়ে কম হয়। কোথায় বসাবে?

প্রথম ধারণা হতে পারে "সবার গড় জায়গায়" (average)। কিন্তু একটু ভাবো — যদি বেশিরভাগ বাড়ি একদিকে জড়ো, আর একটা বাড়ি অনেক দূরে একা থাকে, তাহলে average সেই একা বাড়ির দিকে টেনে যায়, ফলে জড়ো-হওয়া বেশিরভাগ লোককে বেশি হাঁটতে হয়। আসল চালাক জায়গা — মাঝের বাড়িটা (median)। সেখানে বসালে যত লোক বাঁয়ে আর যত লোক ডানে সমান, তাই box-টা একটু সরালেই এক পক্ষের লাভ অন্য পক্ষের সমান-বা-বেশি ক্ষতিতে কাটা পড়ে — অর্থাৎ সরিয়ে আর লাভ নেই। median = ন্যায্যতম মিলনস্থল।

5. Visual explanation¶

nums = [1, 2, 9] (sorted)। target সরালে মোট দূরত্ব কীভাবে বদলায় দেখি:

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 এক ধাপ সরালে বাঁ/ডানে কী ঘটে:

                 বাঁয়ে L টা                ডানে R টা
   ... [x][x][x]   t   [y][y][y][y] ...
            <--- t ডানে সরালে:
            বাঁ-এর L সংখ্যা থেকে +L (দূরত্ব বাড়ে)
            ডান-এর R সংখ্যা থেকে -R (দূরত্ব কমে)
            নিট = L - R।  R>L হলে সরালে লাভ; সমান হলে (=median) থামো।

median-এ এসে বাঁ-ডান ভারসাম্য, তাই আর সরিয়ে লাভ নেই — সেটাই সর্বনিম্ন।

6. Example input and output¶

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-এর মানটা নিলেই হয়।

7. Brute force thinking¶

সবচেয়ে সরল চিন্তা — সম্ভাব্য প্রতিটা target t (array-র সবচেয়ে ছোট থেকে সবচেয়ে বড় মান পর্যন্ত) ধরে মোট দূরত্ব হিসাব করো, সবচেয়ে ছোটটা রাখো:

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 ঘুরে দূরত্ব — সব মিলিয়ে অসম্ভব ধীর।

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 বের করো, আর সেখানকার মোট দূরত্ব যোগ করো:

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 নয়।

11. Step-by-step dry run¶

nums = [1, 0, 0, 8, 6] ধরে median পথে চালাই:

শুরুর অবস্থা: array [1, 0, 0, 8, 6], length 5।
sort: s = [0, 0, 1, 6, 8]।
median index = len(s) // 2 = 5 // 2 = 2 → s[2] = 1। তাই target = 1।
প্রতিটা থেকে দূরত্ব: |0−1| + |0−1| + |1−1| + |6−1| + |8−1| = 1 + 1 + 0 + 5 + 7।
যোগফল = 14।

মানে সবাইকে 1-এ আনতে 14 move লাগবে, আর এটাই সর্বনিম্ন — brute force-এর সাথে মিলে গেল। (যাচাই: target 0 নিলে 0+0+1+8+6 = 15, target 6 নিলে 6+6+5+0+2 = 19 — দুটোই বেশি; median-ই জেতে।)

12. Python solution¶

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¶

if not nums: return 0

ফাঁকা array-তে কিছু সমান করার নেই — 0 move। (এই guard না থাকলে নিচে s[len(s)//2] খালি list-এ index error দিত।)

s = sorted(nums)

median বের করতে আগে sort করি। sort করায় মাঝের উপাদানটাই median হয়ে যায় — খুঁজে বের করা সহজ।

median = s[len(s) // 2]

মধ্যমা = sorted array-র মাঝের উপাদান। বিজোড় দৈর্ঘ্যে এটা ঠিক মাঝেরটা; জোড় দৈর্ঘ্যে এটা মাঝের দুটোর মধ্যে ডানেরটা — কিন্তু জোড়ে মাঝের যেকোনো মানই সমান সর্বনিম্ন দূরত্ব দেয়, তাই এটাই যথেষ্ট (আলাদা গড় নেওয়ার দরকার নেই)।

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!।

14. Output walkthrough¶

চালালে যা ছাপবে:

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 সব কেসে সর্বনিম্ন দিয়েছে।

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¶

average নেওয়া — দূরত্ব minimize করে median, mean নয়। average নিলে outlier-এ ভুল উত্তর (যেমন [1, 2, 9]-এ average 4, কিন্তু সেরা target 2)।
জোড় দৈর্ঘ্যে দুই median-এর গড় বের করা — জোড়ে মাঝের যেকোনো মান (এমনকি s[n//2]) সমান সর্বনিম্ন দেয়; গড় বের করার দরকার নেই (আর integer move-এ গড় ভগ্নাংশ হলে ঝামেলা)।
median-এর বদলে min বা max-এ আনা — দুই প্রান্তে আনলে দূরত্ব সবচেয়ে বেশি; ঠিক উল্টো ভুল।
negative সংখ্যা ভুলে যাওয়া — |x − t| negative মানেও ঠিক কাজ করে; শুধু absolute নিতে ভুলো না।
ফাঁকা array না সামলানো — খালি list-এ s[len(s)//2] index error; গোড়ায় return 0।

18. Harder problems that inherit this idea¶

CSES — Stick Lengths (https://cses.fi/problemset/task/1074) — হুবহু একই: সব stick সমান করতে ন্যূনতম খরচ = median target।
LeetCode — Minimum Moves to Equal Array Elements II (https://leetcode.com/problems/minimum-moves-to-equal-array-elements-ii/) — এটাই মূল problem।
LeetCode — Best Position for a Service Centre (https://leetcode.com/problems/best-position-for-a-service-centre/) — 2D-তে geometric median; একই "দূরত্ব-যোগফল minimize" ধারণার উন্নত রূপ।

19. Pattern learned¶

Median minimizes sum of absolute distances — সবাইকে এক বিন্দুতে আনতে (খরচ = দূরত্ব) সেরা target হলো median; খরচ = Σ |x − median|। বড় শিক্ষা: L1 (absolute) দূরত্ব → median; L2 (বর্গ) দূরত্ব → mean — কোন norm minimize করছ সেটাই target ঠিক করে। আর কেন median: target সরালে লাভ-ক্ষতি নির্ভর করে দুই পাশের সংখ্যার ভারসাম্যে, মানে নয়।

20. Final summary¶

ভবিষ্যতের আমাকে এক লাইনে: "সব সমান করতে ±1 move minimize = target median; sort করে s[n//2], তারপর Σ|x − median|। Signal: 'প্রতি ধাপ খরচ = দূরত্ব, সবাইকে এক বিন্দুতে' দেখলেই median মনে পড়ুক (average নয়!) — কারণ target সরালে ভারসাম্য দুই পাশের গণনায়, মানে নয়।"

পরের ধাপ → 112 — Minimize Maximum Difference (sort + adjacent / BSoA মোচড়)। ভিত্তি/সম্পর্কিত → 110 — Maximum Product by Splitting (একই exchange-argument দর্শন)।

ফিরে দেখা: এই level-এর map → ../README.md · এই note-টা যে ছকে লেখা → ../../../templates/math-problem-note-template.md।

মনে রাখার নিয়ম (legal): সব নিজের ভাষায় লেখো; problem statement copy কোরো না; official link শুধু attribution-এর জন্য রাখো; "asked by Google/Amazon" এমন দাবি কোরো না — বরং "Google-style pattern" / "common interview pattern" লেখো।