C++-এ দুটি সর্টেড অ্যারে থেকে সবচেয়ে কাছের যুগল বের করা

দুটি সর্টেড অ্যারে এবং একটি সংখ্যা 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-এর ডান থেকে শুরু করব, তারপর নিচের ধাপগুলো ফলো করব যেন এমন যুগল পাওয়া যায়:

• diff আরম্ভ করুন, এটি যুগল এবং x-এর মধ্যে পার্থক্য ধারণ করবে।
• দুটি পয়েন্টার আরম্ভ করুন left := 0 এবং right := n - 1।
• যখন left <= m এবং right >= 0, তখন করুন:
  • যদি |A1[left] + A2[right] - sum| < diff হয়, তবে:
    • diff এবং রেজাল্ট আপডেট করুন।
  • যদি (A1[left] + A2[right]) < sum হয়, তবে:
    • left ১ বাড়ান।
  • অন্যথায়:
    • right ১ কমান।
• রেজাল্ট দেখান।

উদাহরণ

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