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

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

উদাহরণ

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

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

অ্যালগরিদম

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

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

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

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

// Efficient Two Pointer O(n)
int countPairsTwoPointer(int arr[], int n, int k) {
    sort(arr, arr + n); // Ensure sorted
    int count = 0;
    int left = 0, right = n - 1;
    
    while (left < right) {
        if (1LL * arr[left] * arr[right] < k) {
            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 k = 10;
    
    cout << "Naive: " << countPairsNaive(arr, n, k) << endl;
    cout << "Two Pointer: " << countPairsTwoPointer(arr, n, k);
    return 0;
}

ইনপুট

[2, 7, 1, 0, 8], k = 10

আউটপুট

7