পাইথনে লিস্টের সব এলিমেন্ট একই করার জন্য ন্যূনতম অপারেশন গণনা

সমস্যা বিবরণ

একটি ইন্টিজার লিস্ট nums দেওয়া আছে। প্রতিটি অপারেশনে সবচেয়ে বড় সংখ্যাটি দ্বিতীয় বড় সংখ্যায় কনভার্ট করতে পারেন। সব সংখ্যা একই করার জন্য ন্যূনতম অপারেশন সংখ্যা বের করতে হবে।

উদাহরণ

Input:  nums = [5, 9, 2]
Output: 3
ব্যাখ্যা:
Step 1: 9 → 5  → [5, 5, 2]
Step 2: 5 → 2  → [5, 2, 2] (একটি 5)
Step 3: 5 → 2  → [2, 2, 2] (অন্য 5)
Total: 3 operations

কী অভিজ্ঞতা (Key Insight)

প্রতিটি অপারেশনে একটি এলিমেন্ট এক ধাপ নিচে আসে (সর্টেড ইউনিক ভ্যালুতে)। তাই প্রতিটি এলিমেন্টের জন্য তার র‍্যাঙ্ক (sorted unique-এ ইনডেক্স) তার অপারেশন সংখ্যা।

অ্যালগরিদম

1. ইউনিক ভ্যালু গুলো সর্ট করুন: vals = sorted(set(nums))
2. ভ্যালু → র‍্যাঙ্ক ম্যাপ বানান: vtoi = {v: i for i, v in enumerate(vals)}
3. সব এলিমেন্টের র‍্যাঙ্ক যোগফল = টোটাল অপারেশন

পাইথন কোড

class Solution:
    def solve(self, nums):
        vals = sorted(set(nums))
        vtoi = {v: i for i, v in enumerate(vals)}
        return sum(vtoi[v] for v in nums)

ob = Solution()
nums = [5, 9, 2]
print(ob.solve(nums))  # 3

ড্রাই রান

nums = [5, 9, 2]
vals = sorted(set(nums)) = [2, 5, 9]
vtoi = {2: 0, 5: 1, 9: 2}

sum = vtoi[5] + vtoi[9] + vtoi[2]
    = 1 + 2 + 0 = 3

জটিলতা বিশ্লেষণ

• সময় জটিলতা: O(n log n) — সর্টিং 때문ে
• স্থান জটিলতা: O(u) — u = ইউনিক ভ্যালু সংখ্যা

উপসংহার

• অপারেশন = এলিমেন্টকে ছোট ভ্যালুতে নামানো
• র‍্যাঙ্ক = সর্টেড ইউনিক লিস্টে ইনডেক্স
• মաթেম্যাটিক্যাল ইনসাইট দিয়ে O(n log n) সমাধান