পাইথনে রঙ মার্জ করলে অবশিষ্ট ন্যূনতম রঙের সংখ্যা বের করার প্রোগ্রাম

একটি রঙের লিস্ট colors দেওয়া আছে (R, G, B)। দুটি ভিন্ন রঙ পাশাপাশি থাকলে তারা থার্ড রঙে রূপান্তরিত হতে পারে (যেমন R+G=B, G+B=R, B+R=G)। যেকোনো সিকোয়েন্সে মার্জ করার পর অবশিষ্ট ন্যূনতম রঙের সংখ্যা বের করতে হবে।

উদাহরণস্বরূপ, colors = ["G","R","G","B","R"] হলে আউটপুট ১।

সমাধানের পদ্ধতি (XOR-বেজড ম্যাথematical ট্রিক)

রঙগুলোকে নাম্বার ম্যাপ করুন: R=1, G=2, B=3। সকল রঙের XOR নিন। যদি XOR ০ হয়, তবে উত্তর ২, অন্যথায় ১। (যদি সব রঙ একই হয়, তবে উত্তর n)।

পাইথন কোড উদাহরণ

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