সমস্যা বিবৃতি
সমান আকারের N দুটি অ্যারের দেওয়া, তাদের উপাদানগুলি ব্যবহার করে সর্বাধিক সংখ্যক জোড়া তৈরি করুন, একটি প্রথম অ্যারে থেকে এবং দ্বিতীয়টি দ্বিতীয় অ্যারে থেকে, যাতে প্রতিটি অ্যারের থেকে একটি উপাদান সর্বাধিক একবার ব্যবহার করা হয় এবং নির্বাচিতগুলির মধ্যে পরম পার্থক্য একটি জোড়া গঠনের জন্য ব্যবহৃত উপাদানগুলি একটি প্রদত্ত উপাদান K এর থেকে কম বা সমান।
উদাহরণ
যদি ইনপুট হয় −
arr1[] ={3, 4, 5, 2, 1}
arr2[] ={6, 5, 4, 7, 15}
এবং k =3 তাহলে আমরা নিম্নলিখিত 4 টি জোড়া গঠন করতে পারি যার পরম পার্থক্য 3 এর থেকে কম বা সমান -
(1, 4), (2, 5), (3, 6), (4, 7)
অ্যালগরিদম
আমরা এই সমস্যা সমাধানের জন্য পুনরাবৃত্তিমূলক পদ্ধতি ব্যবহার করতে পারি
- উভয় অ্যারে সাজান
- প্রথম অ্যারের প্রতিটি উপাদানকে সম্ভাব্য জোড়ার জন্য দ্বিতীয় অ্যারের প্রতিটি উপাদানের সাথে তুলনা করুন, যদি একটি জোড়া তৈরি করা সম্ভব হয়
- প্রথম অ্যারের পরবর্তী উপাদানের জন্য পরবর্তী সম্ভাব্য জোড়ার জন্য পরীক্ষা চালিয়ে যান৷
উদাহরণ
আসুন এখন একটি উদাহরণ দেখি -
#include <bits/stdc++.h>
using namespace std;
int getMaxUniquePairs(int *arr1, int *arr2, int n, int k) {
sort(arr1, arr1 + n);
sort(arr2, arr2 + n);
bool visited[n];
memset(visited, false, sizeof(visited));
int pairCnt = 0;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
if (abs(arr1[i] - arr2[j]) <= k &&
visited[j] == false) {
++pairCnt;
visited[j] = true;
break;
}
}
}
return pairCnt;
}
int main() {
int arr1[] = {3, 4, 5, 2, 1};
int arr2[] = {6, 5, 4, 7, 15};
int n = sizeof(arr1) / sizeof(arr1[0]);
int k = 3;
cout << "Maximum unique pairs = " << getMaxUniquePairs(arr1, arr2, n, k) << endl;
return 0;
} আউটপুট
Maximum unique pairs = 4
