পাইথনে ম্যাট্রিক্স থেকে ভিন্ন সারির উপাদান দিয়ে সমান সম্বলিত পেয়ার খুঁজে বের করা

একটি ম্যাট্রিক্স দেওয়া আছে যেটে সব উপাদান ইউনিক (unique)। একটি টার্গেট সম (sum) দেওয়া আছে। ম্যাট্রিক্স থেকে যেসব পেয়ারের যোগফল টার্গেট সমের সমান, সেগুলো খুঁজে বের করতে হবে। শর্ত: পেয়ারের দুটি উপাদান ভিন্ন সারির (different rows) হতে হবে।

উদাহরণ

ম্যাট্রিক্স: [[2, 4, 3, 5], [6, 9, 8, 7], [10, 11, 14, 12], [13, 1, 15, 16]] Sum = 13

আউটপুট: [(2, 11), (4, 9), (3, 10), (5, 8), (12, 1)]

সমাধানের পদ্ধতি

1. প্রতিটি সারি আলাদা আলাদা সাজানো (sort) করা হয়।
2. সáros সারি জোড়া (pair of rows) নিয়ে টু-পয়েন্টার টেকনিক প্রয়োগ করা হয়।
3. এক সারির শুরু (low) এবং অন্য সারির শেষ (high) থেকে শুরু করা হয়।
4. যোগফল মিললে পেয়ার সংরক্ষণ, low++, high--। যোগফল কম হলে low++, বেশি হলে high--।

পাইথন কোড

def sum_pair(matrix, target_sum):
    res = []
    n = len(matrix)
    for i in range(n):
        matrix[i].sort()
    
    for i in range(n - 1):
        for j in range(i + 1, n):
            low = 0
            high = n - 1
            while low < n and high >= 0:
                s = matrix[i][low] + matrix[j][high]
                if s == target_sum:
                    res.append((matrix[i][low], matrix[j][high]))
                    low += 1
                    high -= 1
                elif s < target_sum:
                    low += 1
                else:
                    high -= 1
    return res

sum_val = 13
matrix = [
    [2, 4, 3, 5],
    [6, 9, 8, 7],
    [10, 11, 14, 12],
    [13, 1, 15, 16]
]
print(sum_pair(matrix, sum_val))

ইনপুট

[[2, 4, 3, 5], [6, 9, 8, 7], [10, 11, 14, 12], [13, 1, 15, 16]], sum = 13

আউটপুট

[(4, 9), (5, 8), (2, 11), (3, 10), (12, 1)]