Đếm cặp (i,j) có tích lớn hơn tổng trong mảng C++

Cho mảng n số dương. Đếm số cặp có thứ tự (i,j) với i < j sao cho arr[i] × arr[j] > arr[i] + arr[j].

Ví dụ minh họa

Ví dụ 1:

• Input: Arr = {1, 1, 2, 3}, N = 4
• Output: 1
• Giải thích: Chỉ cặp (2,3): 2×3=6 > 2+3=5.

Ví dụ 2:

• Input: Arr = {2, 2, 2}, N = 3
• Output: 0
• Giải thích: 2×2=4, 2+2=4, không có cặp nào thỏa mãn >.

Phân tích toán học

Bất đẳng thức: a×b > a+b ⇔ a×b - a - b > 0 ⇔ (a-1)(b-1) > 1

Với a,b là số nguyên dương:

• Nếu a=1 hoặc b=1: (a-1)(b-1)=0 ≯ 1 → Không thỏa mãn
• Nếu a=2, b=2: (1)(1)=1 ≯ 1 → Không thỏa mãn
• Nếu a≥2, b≥3 hoặc a≥3, b≥2: (a-1)(b-1)≥2 > 1 → Thỏa mãn

Mã nguồn C++ (Vét cạn O(n²))

#include <bits/stdc++.h>
using namespace std;

int countPairs(int arr[], int n) {
    int count = 0;
    for (int i = 0; i < n - 1; i++) {
        for (int j = i + 1; j < n; j++) {
            if (arr[i] * arr[j] > arr[i] + arr[j]) {
                count++;
            }
        }
    }
    return count;
}

int main() {
    int arr[] = {1, 2, 3, 2};
    int len = sizeof(arr) / sizeof(int);
    cout << "So cap co tich lon hon tong: " << countPairs(arr, len);
    return 0;
}

Kết quả chạy chương trình

So cap co tich lon hon tong: 2

Tối ưu hóa O(n log n) hoặc O(n)

Sử dụng điều kiện (a-1)(b-1) > 1:

1. Đếm số phần tử = 1 (cnt1), = 2 (cnt2), ≥ 3 (cnt3).
2. Tổng cặp = C(n,2) - cặp không thỏa mãn.
3. Cặp không thỏa mãn: (1, bất kỳ), (2,2).

long long countPairsOptimized(int arr[], int n) {
    long long cnt1 = 0, cnt2 = 0, cnt_ge3 = 0;
    for (int i = 0; i < n; i++) {
        if (arr[i] == 1) cnt1++;
        else if (arr[i] == 2) cnt2++;
        else cnt_ge3++;
    }
    long long total = 1LL * n * (n - 1) / 2;
    long long invalid = cnt1 * (n - 1) + cnt2 * (cnt2 - 1) / 2;
    return total - invalid;
}

Độ phức tạp