Đếm cặp trong mảng có trung bình cộng cũng nằm trong mảng trong C++

Cho mảng số nguyên trong khoảng [-1000, 1000]. Đếm cặp phần tử có trung bình cộng cũng xuất hiện trong mảng. Ví dụ: [1,2,3,4] → (1,3) trung bình 2, (2,4) trung bình 3 → 2 cặp.

Ví dụ

Đầu vào − arr[] = {-1,2,5,-3,8,10}

Đầu ra − 2

Giải thích − (-1,5) avg=2, (2,8) avg=5.

Đầu vào − arr[] = {1,3,2,5,10,6}

Đầu ra − 3

Giải thích − (1,3) avg=2, (1,5) avg=3, (2,10) avg=6.

Phương pháp giải

Tạo mảng tần suất arr_freq kích thước 2001 (dịch chỉ số âm bằng +1000). Với mỗi tần suất >0:

1. Cộng freq*(freq-1)/2 (cặp 2 số bằng nhau, trung bình là chính nó).
2. Duyệt các tần suất cách nhau 2 đơn vị (vì trung bình của 2 số chẵn/lẻ khác nhau là số thực). Nếu freq[i]>0, freq[j]>0, freq[(i+j)/2]>0 → cộng freq[i]*freq[j].

• Hàm average_pair(int arr[], int size).
• N=1000, size_2=2001.
• Điền tần suất: arr_freq[arr[i]+N]++.
• Duyệt i=0..2000, nếu arr_freq[i]>0:
  • count += arr_freq[i]*(arr_freq[i]-1)/2.
  • Với j=i+2; j<2001; j+=2: nếu arr_freq[j]>0 && arr_freq[(i+j)/2]>0 → count += arr_freq[i]*arr_freq[j].
• Trả về count.

Ví dụ code

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

int average_pair(int arr[], int size_1) {
    int count = 0;
    int N = 1000;
    int size_2 = 2 * N + 1;
    int arr_freq[size_2] = {0};
    for (int i = 0; i < size_1; i++) arr_freq[arr[i] + N]++;
    for (int i = 0; i < size_2; i++) {
        if (arr_freq[i] > 0) {
            count += arr_freq[i] * (arr_freq[i] - 1) / 2;
            for (int j = i + 2; j < 2001; j += 2) {
                int mid = arr_freq[(i + j) / 2];
                if (arr_freq[j] > 0 && mid > 0) count += arr_freq[i] * arr_freq[j];
            }
        }
    }
    return count;
}

int main() {
    int arr[] = {2, 3, 1, 8, 9, 10};
    int size = sizeof(arr) / sizeof(arr[0]);
    cout << "Count of pairs with average present in the same array are: " << average_pair(arr, size);
    return 0;
}

Đầu ra

Count of pairs with average present in the same array are: 2