পাইথনে সারি ফ্লিপ করে বাইনারি ম্যাট্রিক্সের সর্বোচ্চ যোগফল বের করার প্রোগ্রাম

সমস্যা বিবরণ

একটি ২D বাইনারি ম্যাট্রিক্স দেওয়া আছে। আমরা যেকোনো সারি বা কলামের সব বিট ফ্লিপ করতে পারি (০ কে ১ এবং ১ কে ০ বদলে দিতে পারি)। এই অপারেশন যেকোনো সংখ্যকবার করা যাবে। প্রতিটি সারি কে একটি বাইনারি নম্বর হিসেবে বিবেচনা করে, আমাদের সম্ভাব্য সর্বোচ্চ যোগফল বের করতে হবে।

উদাহরণ

ইনপুট ম্যাট্রিক্স:

আউটপুট: 11

ব্যাখ্যা: দুটি সারি ফ্লিপ করলে পাওয়া যায় 101 (৫) এবং 110 (৬)। যোগফল = ৫ + ৬ = ১১।

সমাধানের কৌশল

সর্বোচ্চ যোগফল পেতে হলে সবচেয়ে বামের কলাম (MSB) সবসময় ১ রাখতে হবে। তারপর প্রতিটি কলামে ১ এর সংখ্যা সর্বাধিক করা হয়।

অ্যালগরিদম

1. প্রতিটি সারির জন্য:
   • যদি সারির প্রথম উপাদান (MSB) ০ হয়, তবে পুরো সারি ফ্লিপ করুন
2. প্রতিটি কলাম (দ্বিতীয় কলাম থেকে শুরু করে) এর জন্য:
   • কলামে ১ এর সংখ্যা গণনা করুন
   • যদি ০ এর সংখ্যা ১ এর চেয়ে বেশি হয়, তবে কলামটি ফ্লিপ করুন
3. অবশেষে প্রতিটি সারি কে বাইনারি থেকে ডেসিমেলে কনভার্ট করে যোগফল বের করুন

পাইথন কোড

class Solution:
    def solve(self, matrix):
        # ধাপ ১: MSB সবসময় ১ করুন
        for r in matrix:
            if r[0] == 0:
                for i in range(len(r)):
                    r[i] = -r[i] + 1  # ফ্লিপ: 0->1, 1->0
        
        # ধাপ ২: বাকি কলামগুলো অপ্টিমাইজ করুন
        for j in range(1, len(matrix[0])):
            cnt = 0
            for i in range(len(matrix)):
                cnt += 1 if matrix[i][j] else -1
            if cnt < 0:  # ০ বেশি হলে কলাম ফ্লিপ করুন
                for i in range(len(matrix)):
                    matrix[i][j] = -matrix[i][j] + 1
        
        # ধাপ ৩: যোগফল বের করুন
        ans = 0
        for r in matrix:
            a = 0
            for v in r:
                a = 2 * a + v  # বাইনারি থেকে ডেসিমেল
            ans += a
        return ans

ob = Solution()
matrix = [[0, 1, 0], [0, 0, 1]]
print(ob.solve(matrix))  # আউটপুট: 11

জটিলতা বিশ্লেষণ

• সময় জটিলতা: O(R × C) — R = সারি, C = কলাম
• স্থান জটিলতা: O(1) — অতিরিক্ত স্পেস ছাড়া ইন-প্লেস মডিফিকেশন

মূল বিষয়বস্তু

• লালচী (Greedy) কৌশল: MSB সবসময় ১ রাখা óptিমাল
• প্রতিটি কলাম স্বতন্ত্রভাবে অপ্টিমাইজ করা যায়
• বিট ম্যানিপুলেশন এবং বাইনারি সংখ্যা বোঝার সুন্দর উদাহরণ