Cho mảng arr[] kích thước N, đếm số bộ 4 chỉ số (a, b, c, d) sao cho arr[a], arr[b], arr[c] tạo cấp số cộng (AP) và arr[b], arr[c], arr[d] tạo cấp số nhân (GP).
Định nghĩa
- Cấp số cộng (AP): hiệu liên tiếp không đổi. VD: 1, 3, 5, 7 (d=2).
- Cấp số nhân (GP): tỷ số liên tiếp không đổi. VD: 3, 6, 12, 24 (r=2).
Ví dụ
Input: arr[] = {9, 6, 4, 2, 1, 2} Output: 2
Bộ tứ tại chỉ số {3,2,1,0} và {5,2,1,0} → giá trị {2,4,6,9}
Input: arr[] = {2, 6, 1, 4, 2} Output: 2
Bộ tứ tại chỉ số {1,3,0,2} và {1,3,4,2} → giá trị {6,4,2,1}
Phương pháp Brute Force
4 vòng lặp lồng nhau kiểm tra điều kiện AP và GP. Độ phức tạp O(N⁴).
Phương pháp hiệu quả
Dùng unordered_map đếm tần suất các giá trị. Duyệt cặp (b, c) làm số thứ 2 và 3. Số thứ 1: arr[a] = 2*arr[b] - arr[c]. Số thứ 4: arr[d] = arr[c]² / arr[b] (phải chia hết). Kết quả cộng dồn count[arr[a]] * count[arr[d]] (trừ đi 1 nếu trùng chỉ số).
Mã nguồn C++
#include <bits/stdc++.h>
using namespace std;
int main() {
unordered_map<int, int> mp;
int arr[] = {2, 6, 1, 4, 2};
int size = sizeof(arr) / sizeof(arr[0]);
for (int a = 0; a < size; a++)
mp[arr[a]]++;
int count = 0;
for (int b = 0; b < size; b++) {
for (int c = 0; c < size; c++) {
if (b == c) continue;
mp[arr[b]]--; mp[arr[c]]--;
int first = arr[b] - (arr[c] - arr[b]); // 2*b - c
int fourth = (arr[c] * arr[c]) / arr[b];
if ((arr[c] * arr[c]) % arr[b] == 0) {
if (arr[b] != arr[c])
count += mp[first] * mp[fourth];
else
count += mp[first] * (mp[fourth] - 1);
}
mp[arr[b]]++; mp[arr[c]]++;
}
}
cout << "Số bộ bốn: " << count;
return 0;
}
Kết quả
Số bộ bốn: 2
Giải thích
Với b, c cố định, a và d được xác định duy nhất bởi điều kiện AP và GP. Dùng map đếm tần suất để tính số cách chọn a và d từ các phần tử còn lại. Độ phức tạp O(N²).
Kết luận
Bài viết giải quyết bài toán đếm bộ 4 với 3 số đầu AP, 3 sau GP. So sánh Brute Force O(N⁴) và phương pháp tối ưu O(N²) dùng hash map. Mã C++ đầy đủ, có thể chuyển sang ngôn ngữ khác.