C++-এ অ্যারেতে x

সিম্পল O(n²) পদ্ধতি

int X_Less_Y(int arr[], int size) {
    int count = 0;
    for (int i = 0; i < size; i++)
        for (int j = 0; j < size; j++)
            if (arr[i] < arr[j]) count++;
    return count;
}

অপ্টিমাইজড O(n log n) পদ্ধতি

1. অ্যারে সর্ট করুন।
2. প্রতিটি উপাদানের জন্য, তার চেয়ে বড় উপাদানগুলো বাইনারি সার্চ/দুই পয়েন্টার দিয়ে খুঁজুন।
3. অথবা: সর্টেড অ্যারেতে প্রতিটি উপাদানের জন্য তার ডানপাশে কতটি আছে তা যোগ করুন।

C++ বাস্তবায়ন (অপ্টিমাইজড)

#include 
using namespace std;

long long countPairs(vector& arr) {
    sort(arr.begin(), arr.end());
    long long ans = 0;
    int n = arr.size();
    for (int i = 0; i < n; i++) {
        // arr[i] < arr[j] হলে j > i এবং arr[j] > arr[i]
        auto it = upper_bound(arr.begin() + i + 1, arr.end(), arr[i]);
        ans += arr.end() - it;
    }
    return ans;
}

int main() {
    vector v = {2, 4, 3, 1};
    cout << countPairs(v); // 6
    return 0;
}