पायथन में k टावरों को समान ऊंचाई का बनाने के लिए न्यूनतम ईंटों की संख्या खोजने का प्रोग्राम

मान लीजिए हमारे पास टावर ऊंचाइयों की एक सूची है, और एक धनात्मक मान k। हम k टावरों का चयन करना चाहते हैं और अधिक ईंटें जोड़कर उन सभी को समान ऊंचाई का बनाना चाहते हैं, लेकिन यथासंभव कम ईंटों का उपयोग करके। हमें k टावरों को चुनकर उन्हें समान ऊंचाई का बनाने के लिए आवश्यक न्यूनतम ईंटों की संख्या ढूंढनी है।

उदाहरण के लिए, यदि इनपुट heights = [4, 7, 31, 14, 40] और k = 3 है, तो आउटपुट 17 होगा, क्योंकि हम 5, 8, और 15 चुन सकते हैं जिन्हें समान ऊंचाई का बनाने के लिए 17 ईंटों की आवश्यकता होती है।

समाधान दृष्टिकोण

इसे हल करने के लिए हम निम्नलिखित चरणों का पालन करेंगे (स्लाइडिंग विंडो + सॉर्टिंग):

heights को सॉर्ट करें
ans := infinity
s := 0 (विंडो सम)
प्रत्येक इंडेक्स i और मान x के लिए heights में:
- s += x
- यदि i >= k: s -= heights[i-k]
- यदि i >= k-1:
  - ans := min(ans, x*k - s)
ans लौटाएं

उदाहरण कोड

class Solution:
    def solve(self, heights, k):
        heights.sort()
        ans = float("inf")
        s = 0
        for i, x in enumerate(heights):
            s += x
            if i >= k:
                s -= heights[i-k]
            if i >= k-1:
                ans = min(ans, x*k - s)
        return ans

ob = Solution()
heights = [5, 8, 32, 15, 41]
k = 3
print(ob.solve(heights, k))

इनपुट

[5, 8, 32, 15, 41], 3