Đếm số bộ ba (triplets) có tích nhỏ nhất trong mảng C++

Cho mảng Arr[]. Đếm số bộ ba (i

Ví dụ minh họa

Ví dụ 1:

• Input: arr = {1, 2, 3, 2, 4, 1, 5}
• Output: 2
• Giải thích: Tích nhỏ nhất = 2. Các bộ ba: (1,2,1) xuất hiện 2 cách (2 số 1, 2 số 2).

Ví dụ 2:

• Input: arr = {1, 1, 2, 1, 2, 2}
• Output: 1
• Giải thích: Tích nhỏ nhất = 1. Chỉ bộ ba (1,1,1) - cần 3 số 1, mảng có 3 số 1 → 1 cách.

Mã nguồn C++ (Hai lần duyệt O(n³))

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

int countTriplets(int arr[], int n) {
    int count = 0;
    int minprod = INT_MAX;
    
    // Lần 1: Tìm tích nhỏ nhất
    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++) {
                int prod = arr[i] * arr[j] * arr[k];
                if (prod < minprod) minprod = prod;
            }
        }
    }
    
    // Lần 2: Đếm bộ ba có tích = minprod
    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++) {
                int prod = arr[i] * arr[j] * arr[k];
                if (prod == minprod) count++;
            }
        }
    }
    return count;
}

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

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

So bo ba co tich nho nhat: 2

Tối ưu hóa O(n log n) - Sắp xếp + Tổ hợp

Tích nhỏ nhất sẽ đến từ 3 số nhỏ nhất (sau khi sắp xếp).

Sắp xếp mảng: a₀ ≤ a₁ ≤ a₂ ≤ ...

Tích nhỏ nhất = a₀ × a₁ × a₂.

Đếm số cách chọn 3 phần tử cho tích này:

• Nếu a₀ < a₁ < a₂: cnt[a₀] × cnt[a₁] × cnt[a₂]
• Nếu a₀ = a₁ = a₂: C(cnt[a₀], 3)
• Nếu a₀ = a₁ < a₂: C(cnt[a₀], 2) × cnt[a₂]
• Nếu a₀ < a₁ = a₂: cnt[a₀] × C(cnt[a₁], 2)

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

long long nCk(long long n, int k) {
    if (n < k) return 0;
    if (k == 2) return n * (n - 1) / 2;
    if (k == 3) return n * (n - 1) * (n - 2) / 6;
    return 0;
}

long long countTripletsOptimized(int arr[], int n) {
    sort(arr, arr + n);
    unordered_map freq;
    for (int i = 0; i < n; i++) freq[arr[i]]++;
    
    int x = arr[0], y = arr[1], z = arr[2];
    
    if (x == y && y == z) return nCk(freq[x], 3);
    if (x == y) return nCk(freq[x], 2) * freq[z];
    if (y == z) return freq[x] * nCk(freq[y], 2);
    return 1LL * freq[x] * freq[y] * freq[z];
}

Độ phức tạp