Đếm cặp (x,y) trong mảng với x < y trong C++

Cho mảng số nguyên. Đếm số cặp có thứ tự (x,y) (x và y lấy từ mảng, có thể trùng vị trí) sao cho x < y.

Ví dụ: {2,4,3,1} → 6.

Giải thuật: Vòng lặp lồng O(n^2), đếm arr[i] < arr[j].

Ví dụ

#include <iostream>
using namespace std;

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;
}

int main() {
    int arr[] = {2,4,3,1};
    int size = sizeof(arr) / sizeof(arr[0]);
    cout << "Count: " << X_Less_Y(arr, size);
    return 0;
}

Đầu ra

Count of pairs (x, y) in an array such that x < y are: 6