C++-এ ম্যাট্রিক্সে দিয়ে যোজন যোগফলের জোড়া খুঁজুন

একটি ম্যাট্রিক্স এবং একটি টার্গেট সম দেওয়া আছে। ম্যাট্রিক্সে এমন একটি জোড়া খুঁজতে হবে যাদের যোগফল টার্গেট সমের সমান।

উদাহরণ

• ইনপুট: matrix = {{4,6,4,65},{56,1,12,32},{4,5,6,44},{13,9,11,25}}, SUM=20 → আউটপুট: Pair exists (৯+১১=২০)
• ইনপুট: matrix = {{5,7,3,45},{63,5,3,7},{11,6,9,5},{8,6,14,15}}, SUM=13 → আউটপুট: Pair does not exist

অ্যালগরিদম

১. ব্রুট-ফোর্স (O(N²M²))

সব জোড়া চেক করুন। সহজ কিন্তু ধীর।

২. হ্যাশ সেট দিয়ে ইফিশিয়েন্ট (O(NM))

1. একটি unordered_set বানান।
2. ম্যাট্রিক্স ট্রাভার্স করুন।
3. প্রতিটি এলিমেন্ট x-এর জন্য চেক করুন SUM - x সেটে আছে কিনা।
4. আছে → জোড়া পাওয়া গেলো। নেই → x সেটে ইনসার্ট করুন।

C++ প্রোগ্রাম

#include <bits/stdc++.h>
using namespace std;
#define n 4
#define m 4

int main() {
    int matrix[n][m] = {
        {5,7,3,45},
        {63,5,3,7},
        {11,6,9,5},
        {8,6,14,15}
    };
    int sum = 7;
    unordered_set<int> hash;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (hash.find(sum - matrix[i][j]) != hash.end()) {
                cout << "Pair exists." << endl;
                return 0;
            } else {
                hash.insert(matrix[i][j]);
            }
        }
    }
    cout << "Pair does not exist." << endl;
    return 0;
}

আউটপুট

Pair does not exist.

কোড ব্যাখ্যা

• unordered_set O(1) এवरেজ লুকআপ দেয়।
• hash.find(sum - matrix[i][j]) চেক করে কামপ্লিমেন্ট আছে কিনা।
• পাওয়া গেলে তৎক্ষণ রিটার্ন।
• সম্পূর্ণ ট্রাভার্সালের পরও না পেলে "does not exist"।

কমপ্লেক্সিটি

হ্যাশ সেট পদ্ধতিই বড় ম্যাট্রিক্সের জন্য প্রায়োগিক।