पायथन में मर्जिंग के बाद न्यूनतम रंगों की संख्या खोजने का प्रोग्राम

मान लीजिए हमारे पास रंगों (R, G, B) की एक लिस्ट है। अब यदि दो अलग-अलग रंग अगल-बगल हैं तो वे तीसरे रंग के एकल रंग आइटम में बदल सकते हैं। हमें किसी भी संभावित परिवर्तन अनुक्रम के बाद शेष सबसे छोटी संख्या ढूंढनी है।

उदाहरण के लिए, यदि इनपुट colors = ["G", "R", "G", "B", "R"] है, तो आउटपुट 1 होगा क्योंकि यह नीचे दिखाए अनुसार बदल सकता है:

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

इस समस्या को हल करने के लिए हम XOR ऑपरेशन का उपयोग करेंगे:

• n := colors का आकार
• यदि colors में केवल एक विशिष्ट रंग है, तो n लौटाएं
• यदि n <= 1 है, तो n लौटाएं
• x := 0
• d := की-वैल्यू पेयर वाला मैप: {("R", 1), ("G", 2), ("B", 3)}
• colors में प्रत्येक c के लिए: x := x XOR d[c]
• यदि x == 0 है तो 2 लौटाएं अन्यथा 1

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

class Solution:
    def solve(self, colors):
        n = len(colors)
        if len(set(colors)) == 1:
            return n
        if n <= 1:
            return n
        x = 0
        d = {"R": 1, "G": 2, "B": 3}
        for qux in colors:
            x ^= d[qux]
        return 2 if x == 0 else 1

ob = Solution()
colors = ["G", "R", "G", "B", "R"]
print(ob.solve(colors))

इनपुट

["G", "R", "G", "B", "R"]

आउटपुट

1