पायथन में कॉलम फ्लिप करके टारगेट मैट्रिक्स बनाने के लिए न्यूनतम ऑपरेशन गिनने का प्रोग्राम

मान लीजिए हमारे पास एक मैट्रिक्स M और एक टारगेट मैट्रिक्स T है जिसमें समान संख्या में पंक्तियां और स्तंभ हैं। अब एक ऑपरेशन मान लें जहां हम मैट्रिक्स में एक विशेष कॉलम को फ्लिप करते हैं ताकि सभी 1, 0 में बदल जाएं और सभी 0, 1 में बदल जाएं। तो अगर हम मैट्रिक्स की पंक्तियों को मुफ्त में पुनः क्रमबद्ध कर सकते हैं, तो M को T में बदलने के लिए आवश्यक न्यूनतम ऑपरेशनों की संख्या ढूंढें। यदि कोई समाधान नहीं है, तो -1 वापस करें।

उदाहरण के लिए, यदि इनपुट M = [[0,0],[1,0],[1,1]] और T = [[0,1],[1,0],[1,1]] है, तो आउटपुट 1 होगा।

इसे हल करने के लिए हम निम्न चरणों का पालन करेंगे:

• nums1 := एक नई सूची, nums2 := एक नई सूची
• मैट्रिक्स में प्रत्येक पंक्ति के लिए करें:
  • ths := 0
  • जब तक पंक्ति खाली नहीं है, करें:
    • ths := (ths*2) + पंक्ति का अंतिम तत्व, और पंक्ति का अंतिम तत्व हटाएं
  • nums1 के अंत में ths डालें
• टारगेट में प्रत्येक पंक्ति के लिए करें:
  • ths := 0
  • जब तक पंक्ति शून्येतर है, करें:
    • ths := (ths*2) + पंक्ति का अंतिम तत्व, और पंक्ति का अंतिम तत्व हटाएं
  • nums2 के अंत में ths डालें
• ret := अनंत
• nums1 में प्रत्येक num के लिए करें:
  • cts := nums1 में विशिष्ट तत्वों और उनकी आवृत्तियों का मैप
  • cts[num] := cts[num] - 1
  • my_xor := num XOR nums2[0]
  • i को 1 से nums2 के आकार तक के लिए करें:
    • needed := my_xor XOR nums2[i]
    • यदि cts[needed] शून्य है, तो लूप से बाहर निकलें
    • cts[needed] := cts[needed] - 1
  • अन्यथा, ret := min(ret, my_xor के सेट बिट्स की संख्या)
• ret वापस करें यदि ret अनंत के बराबर नहीं है अन्यथा -1

उदाहरण

class Solution:
    def solve(self, matrix, target):
        nums1 = []
        nums2 = []
        for row in matrix:
            ths = 0
            while row:
                ths = (ths << 1) + row.pop()
            nums1.append(ths)
        for row in target:
            ths = 0
            while row:
                ths = (ths << 1) + row.pop()
            nums2.append(ths)
        ret = float('inf')
        from collections import Counter
        for num in nums1:
            cts = Counter(nums1)
            cts[num] -= 1
            my_xor = num ^ nums2[0]
            for i in range(1, len(nums2)):
                needed = my_xor ^ nums2[i]
                if not cts[needed]:
                    break
                cts[needed] -= 1
            else:
                ret = min(ret, bin(my_xor).count('1'))
        return ret if ret != float('inf') else -1

ob = Solution()
M = [[0,0],[1,0],[1,1]]
T = [[0,1],[1,0],[1,1]]
print(ob.solve(M, T))

इनपुट

M = [[0,0],[1,0],[1,1]] T = [[0,1],[1,0],[1,1]]

आउटपुट

1