সর্টেড অ্যারে-এ যোগফল কম থাকা জোড়া গণনা C++-এ

একটি সর্টেড অ্যারে এবং একটি মান x দেওয়া থাকলে, কতটি জোড়ার যোগফল x-এর চেয়ে কম তা গণনা করতে হবে।

উদাহরণ

ইনপুট: arr = [2, 7, 1, 0, 8], x = 8 (সর্টেড: [0, 1, 2, 7, 8])

বৈধ জোড়া (যোগফল < 8): (0,1), (0,2), (0,7), (1,2) → মোট 4টি

অ্যালগরিদম

1. সাধারণ (O(n²)): নেস্টেড লুপে সব জোড়া চেক করুন।
2. দক্ষ (O(n)) - টু পয়েন্টার:
   • দুটি পয়েন্টার: left = 0, right = n-1
   • যদি arr[left] + arr[right] < x হয়, তবে left থেকে right পর্যন্ত সব জোড়া বৈধ → কাউন্ট += (right - left), left++
   • অন্যথায় right--

C++ কোড উদাহরণ (দুই পদ্ধতি)

#include <iostream>
#include <algorithm>
using namespace std;

// Naive O(n²)
int countPairsNaive(int arr[], int n, int x) {
    int count = 0;
    for (int i = 0; i < n; i++)
        for (int j = i+1; j < n; j++)
            if (arr[i] + arr[j] < x) count++;
    return count;
}

// Efficient Two Pointer O(n)
int countPairsTwoPointer(int arr[], int n, int x) {
    sort(arr, arr + n); // Ensure sorted
    int count = 0;
    int left = 0, right = n - 1;
    
    while (left < right) {
        if (arr[left] + arr[right] < x) {
            count += (right - left);
            left++;
        } else {
            right--;
        }
    }
    return count;
}

int main() {
    int arr[] = {2, 7, 1, 0, 8};
    int n = sizeof(arr) / sizeof(arr[0]);
    int x = 8;
    
    cout << "Naive: " << countPairsNaive(arr, n, x) << endl;
    cout << "Two Pointer: " << countPairsTwoPointer(arr, n, x);
    return 0;
}

ইনপুট

[2, 7, 1, 0, 8], x = 8

আউটপুট

4