पायथन में बाइनरी मैट्रिक्स में कॉलम फ्लिप करके अधिकतम समान पंक्तियाँ प्राप्त करने का प्रोग्राम

एक बाइनरी मैट्रिक्स दिया गया है। हम किसी भी संख्या में कॉलम चुन सकते हैं और उस कॉलम के प्रत्येक सेल को फ्लिप कर सकते हैं (0 को 1 में, 1 को 0 में)। लक्ष्य अधिकतम संख्या में ऐसी पंक्तियाँ प्राप्त करना है जिनके सभी मान समान हों (सभी 0 या सभी 1)।

उदाहरण

इनपुट मैट्रिक्स:

[[0, 0, 0],
 [0, 0, 1],
 [1, 1, 0]]

आउटपुट: 2

व्याख्या: पहले दो कॉलम फ्लिप करने पर मैट्रिक्स बन जाता है:

[[1, 1, 0],
 [1, 1, 1],
 [0, 0, 0]]

अब अंतिम दो पंक्तियाँ ([1,1,1] और [0,0,0]) सभी समान मान वाली हैं।

मुख्य अंतर्दृष्टि

कॉलम फ्लिप करने के बाद, दो पंक्तियाँ समान मान वाली होंगी यदि वे या तो मूल रूप से समान थीं या एक-दूसरे की पूरक (complement) थीं। इसलिए, हम प्रत्येक पंक्ति के लिए उसकी पूरक पंक्ति बनाते हैं और गिनते हैं कि मैट्रिक्स में कितनी पंक्तियाँ मूल या पूरक से मेल खाती हैं।

एल्गोरिदम

1. प्रत्येक पंक्ति row के लिए:
• इसकी पूरक पंक्ति comp बनाएं (प्रत्येक बिट को XOR 1 करें)।
• गिनें कि मैट्रिक्स में कितनी पंक्तियाँ row या comp के बराबर हैं।
• अधिकतम गिनती को अपडेट करें।
2. अधिकतम गिनती वापस करें।

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

class Solution:
    def solve(self, matrix):
        max_rows = 0
        for row in matrix:
            comp = [bit ^ 1 for bit in row]  # पूरक पंक्ति
            count = 0
            for other in matrix:
                if other == row or other == comp:
                    count += 1
            max_rows = max(max_rows, count)
        return max_rows

# परीक्षण
ob = Solution()
matrix = [
    [0, 0, 0],
    [0, 0, 1],
    [1, 1, 0]
]
print(ob.solve(matrix))  # आउटपुट: 2

अनुकूलित संस्करण (हैश मैप)

पंक्तियों को टपल में बदलकर उनकी आवृत्ति गिनें। फिर प्रत्येक अद्वितीय पंक्ति के लिए, उसकी आवृत्ति + उसकी पूरक की आवृत्ति का योग लें। समय जटिलता O(m × n) से O(m × n) ही रहती है लेकिन स्थिरांक कारक बेहतर होता है।

समय जटिलता

• O(m² × n) जहां m पंक्तियों की संख्या है और n स्तंभों की संख्या है।
• हैश मैप के साथ: O(m × n)।