C++-এ দুটি সর্টেড অ্যারে থেকে যোগফল x পাওয়া যাবে এমন জোড়া সংখ্যা গণনা

আমাদের দুটি পজিটিভ সংখ্যার অ্যারে এবং একটি মান x দেওয়া আছে। লক্ষ্য হল জোড়া (A,B) বের করা যাতে A+B=x। এখানে A প্রথম অ্যারে থেকে এবং B দ্বিতীয় অ্যারে থেকে।

উদাহরণ

ইনপুট: arr_1[] = {1,2,5,3,4}, arr_2[] = {7,0,1,3}, x=6

আউটপুট: ২

ব্যাখ্যা: জোড়া: (5,1) এবং (3,3)।

ইনপুট: arr_1[] = {1,1,1}, arr_2[] = {2,2}, x=6

আউটপুট: ২

অ্যালগরিদম (দক্ষ পদ্ধতি - Hash Set)

1. প্রথম অ্যারের সব এলিমেন্ট unordered_set-এ রাখুন।
2. দ্বিতীয় অ্যারে ট্রাভার্স করুন: প্রতিটি arr_2[j] জন্য x - arr_2[j] সেটে আছে কিনা চেক করুন।
3. থাকলে কাউন্ট বাড়ান।
4. সময় জটিলতা: O(n+m)।

C++ বাস্তবায়ন (দক্ষ)

#include <bits/stdc++.h>
using namespace std;

int Pair_value_x(int arr_1[], int arr_2[], int size_arr_1, int size_arr_2, int x) {
    int count = 0;
    unordered_set<int> hash_map;
    
    for (int i = 0; i < size_arr_1; i++) {
        hash_map.insert(arr_1[i]);
    }
    
    for (int j = 0; j < size_arr_2; j++) {
        if (hash_map.find(x - arr_2[j]) != hash_map.end()) {
            count++;
        }
    }
    return count;
}

int main() {
    int arr_1[] = {1, 2, 3, 4};
    int arr_2[] = {2, 3, 4, 5};
    int size_arr_1 = sizeof(arr_1) / sizeof(arr_1[0]);
    int size_arr_2 = sizeof(arr_2) / sizeof(arr_2[0]);
    int x = 6;
    cout << "Count of pairs from two sorted arrays whose sum is equal to a given value x are: " 
         << Pair_value_x(arr_1, arr_2, size_arr_1, size_arr_2, x);
    return 0;
}

আউটপুট

Count of pairs from two sorted arrays whose sum is equal to a given value x are: 4