এই নিবন্ধে, আমরা একটি প্রদত্ত ম্যাট্রিক্সে একটি প্রদত্ত যোগফলের সাথে একটি জোড়া খোঁজার প্রোগ্রাম নিয়ে আলোচনা করব। যেমন −
Input : matrix[n][m] = {
{ 4, 6, 4, 65 },
{ 56, 1, 12, 32 },
{ 4, 5, 6, 44 },
{ 13, 9, 11, 25 }
}, SUM = 20
Output : Pair exists.
Explanation : Sum = 20 is equal to the sum of numbers 9 and 11 which exists in the matrix.
Input : matrix[n][m] = {
{ 5, 7, 3, 45 },
{ 63, 5, 3, 7 },
{ 11, 6, 9, 5 },
{ 8, 6, 14, 15 }
}, SUM = 13
Output : Pair does not exist.
Explanation : No pair exists in the matrix whose sum is equal to 7. সমাধান খোঁজার পদ্ধতি
এখন আমরা উপরের সমস্যার সমাধান খুঁজতে দুটি ভিন্ন পন্থা ব্যাখ্যা করব।
ব্রুট-ফোর্স অ্যাপ্রোচ
প্রদত্ত ম্যাট্রিক্সে প্রতিটি জোড়া বিবেচনা করে এবং জোড়ার যোগফল প্রদত্ত SUM-এর সমান কিনা তা পরীক্ষা করে, যদি হ্যাঁ, তাহলে "পেয়ার বিদ্যমান" প্রিন্ট করুন; অন্যথায়, "জোড়া বিদ্যমান নেই" প্রিন্ট করুন। এই পদ্ধতিটি প্রয়োগ করা খুবই সহজ, কিন্তু এটি সময়ের জটিলতাকে O((N*M)2) এ পরিণত করবে।
দক্ষ পদ্ধতি
সমস্ত ম্যাট্রিক্স উপাদান সংরক্ষণ করার জন্য একটি হ্যাশ ব্যবহার করে এই প্রোগ্রামটি দক্ষ হতে পারে এবং তারপর ম্যাট্রিক্সের মধ্য দিয়ে অতিক্রম করে এবং [ SUM এবং (সূচক উপাদান) ] এর পার্থক্য সমান কিনা তা পরীক্ষা করে দেখতে পারে। যদি হ্যাঁ, তাহলে "Exist" প্রিন্ট করুন এবং প্রোগ্রাম থেকে প্রস্থান করুন। যদি না হয়, তাহলে প্রিন্ট ট্র্যাভার্স করার পরে, "অস্তিত্ব নেই।"
উদাহরণ
#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.
উপরের কোডের ব্যাখ্যা
- 2-ডি অ্যারে ঘোষণা করা এবং এতে উপাদান সংরক্ষণ করা।
- অ্যারের মধ্য দিয়ে ট্রাভার্স করে যদি (সাম - ম্যাট্রিক্স[i][j])!=hash.end().
- যদি শর্তটি সন্তুষ্ট হয়, তাহলে "পেয়ার বিদ্যমান" প্রিন্ট করুন এবং প্রধান ফাংশন থেকে ফিরে আসুন।
- অন্যথায়, অ্যারেটি অতিক্রম করতে থাকুন এবং অবশেষে প্রিন্ট করুন " জোড়া বিদ্যমান নেই।"
উপসংহার
এই নিবন্ধে, আমরা একটি ম্যাট্রিক্স বা 2-ডি অ্যারেতে প্রদত্ত যোগফলের সাথে একটি জোড়া খুঁজে নিয়ে আলোচনা করেছি; আমরা এই সমস্যা সমাধানের জন্য ব্রুট-ফোর্স পদ্ধতি এবং একটি দক্ষ পদ্ধতি নিয়ে আলোচনা করেছি। আমরা এই সমস্যা সমাধানের জন্য C++ প্রোগ্রাম নিয়ে আলোচনা করেছি। যাইহোক, আমরা এই প্রোগ্রামটি অন্য যেকোনো ভাষায় লিখতে পারি যেমন C, Java, Python, ইত্যাদি। আমরা আশা করি আপনার এই নিবন্ধটি সহায়ক হবে।
