Đếm bộ ba (triplets) có tích bằng P (cho phép trùng giá trị, khác chỉ số) C++

Cho mảng Arr[] và số P. Đếm số bộ ba chỉ số (i

Ví dụ minh họa

Ví dụ 1:

• Input: arr = {1, 2, 3, 2, 4, 1, 5}, P = 4
• Output: 3
• Giải thích: (1,2,2) từ chỉ số (0,1,3), (1,4,1) từ (0,4,5), (2,2,1) từ (1,3,5).

Ví dụ 2:

• Input: arr = {1, 1, 2, 1, 2, 2}, P = 8
• Output: 1
• Giải thích: Chỉ (2,2,2) từ 3 số 2.

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

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

int countTriplets(int arr[], int n, int p) {
    int count = 0;
    for (int i = 0; i < n - 2; i++) {
        for (int j = i + 1; j < n - 1; j++) {
            for (int k = j + 1; k < n; k++) {
                if (1LL * arr[i] * arr[j] * arr[k] == p) {
                    count++;
                }
            }
        }
    }
    return count;
}

int main() {
    int Arr[] = {1, 2, 3, 6, 1, 6, 3, 2, 1};
    int N = 9;
    int product = 6;
    cout << "So bo ba co tich = " << product << ": " << countTriplets(Arr, N, product);
    return 0;
}

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

So bo ba co tich = 6: 18

Tối ưu hóa O(n²) - Two Pointers / Hash Map

Với mỗi cặp (i,j), tìm target = P / (arr[i]×arr[j]) trong phần còn lại (nếu chia hết).

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

long long countTripletsOptimized(vector& arr, long long P) {
    int n = arr.size();
    long long count = 0;
    
    // Sắp xếp để dùng two pointers hoặc binary search
    sort(arr.begin(), arr.end());
    
    for (int i = 0; i < n - 2; i++) {
        for (int j = i + 1; j < n - 1; j++) {
            long long prod2 = 1LL * arr[i] * arr[j];
            if (prod2 == 0) {
                if (P == 0) count += (n - j - 1);
                continue;
            }
            if (P % prod2 != 0) continue;
            long long target = P / prod2;
            // Binary search target trong [j+1, n-1]
            auto range = equal_range(arr.begin() + j + 1, arr.end(), target);
            count += range.second - range.first;
        }
    }
    return count;
}

Độ phức tạp

Lưu ý

• Dùng long long cho tích để tránh tràn số (int max ~2×10⁹).
• Xử lý riêng trường hợp P = 0 (cần ít nhất 1 số 0 trong bộ ba).