Đếm cặp trong mảng đã sắp xếp có tích nhỏ hơn k trong C++

Giới thiệu

Cho mảng đã sắp xếp và số k. Đếm số cặp (i, j) với i < j sao cho arr[i] * arr[j] < k.

Ví dụ

• arr = [2,7,1,0,8] (sắp xếp: [0,1,2,7,8]), k = 10 → 7 cặp
• arr = [2,4,6,8], k = 10 → 1 cặp (2,4)

Các cách tiếp cận

Cách 1: Naive O(n²)

Duyệt tất cả cặp, kiểm tra tích.

Cách 2: Hai con trỏ (Two Pointers) O(n) - Chỉ đúng với mảng dương

Vì mảng đã sắp xếp và các phần tử ≥ 0:

• left = 0, right = n-1
• Nếu arr[left] * arr[right] < k: tất cả cặp (left, left+1...right) đều thỏa → cộng right-left, left++
• Ngược lại: right--

Ví dụ triển khai (C++)

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

// Cách 1: Naive
int countProductPairsNaive(vector<int> arr, int k) {
    int count = 0, n = arr.size();
    for (int i = 0; i < n; i++)
        for (int j = i+1; j < n; j++)
            if (arr[i] * arr[j] < k) count++;
    return count;
}

// Cách 2: Two Pointers (chỉ cho mảng không âm)
int countProductPairsTwoPtr(vector<int> arr, int k) {
    sort(arr.begin(), arr.end()); // đảm bảo sắp xếp
    int count = 0, left = 0, right = arr.size() - 1;
    while (left < right) {
        if (1LL * arr[left] * arr[right] < k) {
            count += right - left;
            left++;
        } else {
            right--;
        }
    }
    return count;
}

int main() {
    vector<int> arr = {0, 1, 2, 7, 8};
    int k = 10;
    cout << "Naive: " << countProductPairsNaive(arr, k) << endl;   // 7
    cout << "TwoPtr: " << countProductPairsTwoPtr(arr, k) << endl;  // 7
    return 0;
}

Đầu vào

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

Đầu ra

7