ধরুন আমাদের পূর্ণসংখ্যার একটি তালিকা আছে। আমাদের কাজ হল দুটি জোড়া যেমন (a, b) এবং (c, d) হিসাবে চারটি স্বতন্ত্র পূর্ণসংখ্যা খুঁজে বের করা, যেমন a+b =c+d। যদি একাধিক উত্তর থাকে, তাহলে শুধুমাত্র একটি প্রিন্ট করুন। ধরুন অ্যারের উপাদানগুলি হল:A =[7, 5, 9, 3, 6, 4, 2], তাহলে জোড়া হতে পারে (7, 3) এবং (6, 4)
এখানে আমরা হ্যাশিং টেকনিক ব্যবহার করব। আমরা হ্যাশ টেবিলের মান হিসাবে যোগফল কী হিসাবে জোড়া ব্যবহার করি। এই সমস্যা সমাধানের জন্য আমাদের এই পদক্ষেপগুলি অনুসরণ করতে হবে৷
- আমি 0 থেকে n – 1 রেঞ্জের জন্য, কর
- i + 1 থেকে n – 1 পর্যন্ত j-এর জন্য
- করুন
- সমষ্টি খুঁজুন
- যদি হ্যাশ টেবিলের যোগফল ইতিমধ্যেই থাকে, তাহলে পূর্ববর্তী জোড়া এবং বর্তমান জোড়া মুদ্রণ করুন
- অন্যথায়, হ্যাশ টেবিল আপডেট করুন।
- করুন
উদাহরণ
#include<iostream>
#include<map>
using namespace std;
bool getTwoPairs(int arr[], int n) {
map<int, pair<int, int> > hash_table;
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
int sum = arr[i] + arr[j];
if (hash_table.find(sum) == hash_table.end())
hash_table[sum] = make_pair(i, j);
else {
pair<int, int> pp = hash_table[sum];
cout << "(" << arr[pp.first] << " + " << arr[pp.second] << ") = (" << arr[i] << " + " << arr[j] << ")";
return true;
}
}
}
cout << "No pairs found";
return false;
}
int main() {
int arr[] = {7, 5, 9, 3, 6, 4, 2};
int n = sizeof arr / sizeof arr[0];
cout << "The pairs are: ";
getTwoPairs(arr, n);
} আউটপুট
The pairs are: (7 + 4) = (5 + 6)
