ধরুন আমাদের দুটি সাজানো অ্যারে এবং একটি সংখ্যা x আছে, আমাদের সেই জোড়াটি খুঁজে বের করতে হবে যার যোগফল x এর সবচেয়ে কাছাকাছি। এবং জোড়া প্রতিটি অ্যারে থেকে একটি উপাদান আছে. আমাদের দুটি অ্যারে রয়েছে A1 [0..m-1] এবং A2 [0..n-1], এবং আরেকটি মান x। আমাদের A1[i] + A2[j] জোড়া খুঁজে বের করতে হবে যাতে (A1[i] + A2[j] – x) এর পরম মান সর্বনিম্ন হয়। তাই যদি A1 =[1, 4, 5, 7], এবং A2 =[10, 20, 30, 40], এবং x =32, তাহলে আউটপুট হবে 1 এবং 30।
আমরা A1 এর বাম থেকে এবং A2 থেকে ডানে শুরু করব, তারপর এই ধরনের জোড়া খুঁজে পেতে এই ধাপগুলি অনুসরণ করুন
- ডিফ শুরু করুন, এটি জোড়া এবং x এর মধ্যে পার্থক্য ধরে রাখবে
- বামে দুটি পয়েন্টার শুরু করুন :=0 এবং ডানে :=n – 1
- বামে <=m এবং ডানে>=0, কর
- যদি |A1[বাম] + A2[ডান] – যোগফল|
- ডিফ এবং ফলাফল আপডেট করুন
- যদি |A1[বাম] + A2[ডান] – যোগফল|
- যদি (A1[বাম] + A2[ডান]) <যোগফল, তারপর
- বামে 1 বাড়ান
- অন্যথায়
- ডান 1 দ্বারা হ্রাস করুন
উদাহরণ
#include<iostream>
#include<cmath>
using namespace std;
void findClosestPair(int A1[], int A2[], int m, int n, int x) {
int diff = INT_MAX;
int left_res, right_res;
int left = 0, right = n-1;
while (left<m && right>=0) {
if (abs(A1[left] + A2[right] - x) < diff) {
left_res = left;
right_res = right;
diff = abs(A1[left] + A2[right] - x);
}
if (A1[left] + A2[right] > x)
right--;
else
left++;
}
cout << "The closest pair is [" << A1[left_res] << ", "<< A2[right_res] << "]";
}
int main() {
int ar1[] = {1, 4, 5, 7};
int ar2[] = {10, 20, 30, 40};
int m = sizeof(ar1)/sizeof(ar1[0]);
int n = sizeof(ar2)/sizeof(ar2[0]);
int x = 32;
findClosestPair(ar1, ar2, m, n, x);
} আউটপুট
The closest pair is [1, 30]
