অ্যারেতে চারটি উপাদান a, b, c এবং d খুঁজে বের করা যাতে a+b = c+d C++-তে

মনে করুন আমাদের একটি পূর্ণসংখ্যার তালিকা আছে। আমাদের কাজ হল চারটি ভিন্ন পূর্ণসংখ্যা খুঁজে বের করা যেগুলো দুটি জোড়া (a, b) এবং (c, d) তৈরি করে, যাতে a+b = c+d। যদি একাধিক উত্তর থাকে, তবে শুধু একটি প্রিন্ট করুন। মনে করুন অ্যারে উপাদানগুলো হল: A = [7, 5, 9, 3, 6, 4, 2], তাহলে জোড়াগুলো হতে পারে (7, 3) এবং (6, 4)

এখানে আমরা হ্যাশিং কৌশল ব্যবহার করব। আমরা যোগফলকে কি (key) হিসেবে এবং জোড়াকে মান (value) হিসেবে হ্যাশ টেবিলে রাখব। এই সমস্যাটি সমাধানের জন্য নিচের ধাপগুলো অনুসরণ করতে হবে।

• i = 0 থেকে n-1 পর্যন্ত, করুন
  • j = i+1 থেকে n-1 পর্যন্ত, করুন
    • যোগফল বের করুন
    • যদি হ্যাশ টেবিলে যোগফলটি ইতিমধ্যে থাকে, তবে আগের জোড়া এবং বর্তমান জোড়া প্রিন্ট করুন
    • অন্যথায়, হ্যাশ টেবিল আপডেট করুন।

উদাহরণ

#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)