पायथन में सेल फ्यूजन

समस्या विवरण

संख्याओं की एक सूची cells दी गई है जो सेल्स के आकार दर्शाती है। प्रत्येक इटरेशन में, दो सबसे बड़े सेल्स a और b इंटरैक्ट करते हैं:

• यदि a == b: दोनों मर जाते हैं
• अन्यथा: वे मर्ज होते हैं, नया आकार = floor((a+b)/3)

अंतिम सेल का आकार वापस करें, या -1 यदि कोई सेल न बचे।

उदाहरण

इनपुट: [20, 40, 40, 30]

आउटपुट: 16

व्याख्या: पहले 40 और 40 मर जाते हैं, फिर 20 और 30 → floor(50/3) = 16

एल्गोरिदम (हीप का उपयोग)

1. सभी मानों को नेगेटिव करके मैक्स-हीप बनाएं (पायथन में heapq मिन-हीप है)
2. जब तक हीप में ≥2 तत्व हैं:
   • दो सबसे बड़े निकालें (नेगेटिव करके मूल मान प्राप्त करें)
   • यदि असमान हैं, तो floor((a+b)/3) को नेगेटिव करके हीप में डालें
3. यदि हीप खाली नहीं, तो शेष मान वापस करें (नेगेटिव करके), अन्यथा -1

पायथन कार्यान्वयन

from heapq import heapify, heappop, heappush

class Solution:
    def solve(self, cells):
        cells = [-x for x in cells]
        heapify(cells)
        while len(cells) > 1:
            first, second = -heappop(cells), -heappop(cells)
            if first != second:
                heappush(cells, -((first + second) // 3))
        return -cells[0] if cells else -1

ob = Solution()
cells = [20, 40, 40, 30]
print(ob.solve(cells))

इनपुट

[20, 40, 40, 30]

आउटपुट

16