Chúng ta được cung cấp một mảng các số nguyên sao cho mỗi phần tử của mảng nằm trong khoảng [- 1000,1000]. Mục đích là tìm các cặp phần tử của mảng sao cho giá trị trung bình của chúng cũng có trong mảng đó. Nếu mảng là arr [] =[1,2,3,4]. Khi đó các cặp sẽ là (1,3) và (2,4) vì trung bình của 1,3 là 2 và trung bình của 2,4 là 3 và cả 2 và 3 đều có mặt trong mảng. Số lượng sẽ là 2.
Hãy cho chúng tôi hiểu với các ví dụ.
Đầu vào - arr [] ={-1,2,5, -3,8,10}
Đầu ra - Số lượng các cặp có giá trị trung bình trong cùng một mảng là - 2
Giải thích - Các cặp sao cho giá trị trung bình của chúng có trong arr [] là - (-1,5) trung bình là 2, (2,8) trung bình là 5. Count =2
Đầu vào - arr [] ={1,3,2,5,10,6}
Đầu ra - Số lượng các cặp có giá trị trung bình trong cùng một mảng là - 3
Giải thích - Các cặp sao cho trung bình của chúng có trong arr [] là - (1,3) trung bình là 2, (1,5) trung bình là 3, (2,10) trung bình là 6. Count =3.
Cách tiếp cận được sử dụng trong chương trình dưới đây như sau
Đầu tiên chúng ta sẽ tạo một mảng tần số cho tất cả các phần tử của mảng. Kích thước của mảng tần số gấp đôi kích thước của mảng ban đầu vì cũng có thể có các phần tử âm.
Tần suất của các số âm sẽ bắt đầu từ chỉ số 0 đến chỉ số 1000. Và tần suất của các số dương sẽ bắt đầu từ chỉ số 1000 đến 2000.
Đối với mỗi tần số khác 0, hãy thực hiện điều này -
-
Thêm (freq [i]) * (freq [i] -1) / 2 để đếm, vì giá trị trung bình của hai số giống nhau là chính số đó. Nếu có 5 2’s trong mảng. Khi đó, tổng các cặp sẽ là (5 * (5-1)) / 2 =10.
-
Nếu freq [i] ở trên khác 0 thì bắt đầu duyệt qua các tần số thay thế vì các số liên tiếp có giá trị trung bình là dấu phẩy động và sẽ không có trong mảng.
-
Nếu tìm thấy freq [j] khác 0 và freq [(i + j) / 2] cũng khác 0. Sau đó, thêm freq [i] * freq [j] vào số đếm (vì mỗi số có thể ghép nối với mọi số khác).
-
Lấy một mảng số nguyên arr []
-
Hàm average_pair (arr, size) nhận mảng và kích thước của nó và trả về số lượng các cặp sao cho giá trị trung bình của các phần tử trong cặp cũng có trong mảng arr [].
-
Lấy số lượng ban đầu là 0 và khởi tạo N =1000.
-
Tính độ dài của mảng tần số dưới dạng size_2 =2 * N + 1 (cho dải [-1000 đến 1000]
-
Khởi tạo mảng tần số với 0 ban đầu.
-
Điền mảng tần số sao cho tần số của các phần tử âm là từ 0 đến 1000 và các phần tử dương sau đó. Đối với điều này, hãy thêm N vào chỉ mục.
-
Đối với mỗi phần tử arr [i] cập nhật mảng tần số dưới dạng arr_freq [arr [i] + N] ++;
-
Bây giờ duyệt qua mảng tần số từ i =0 đến i
-
Đối với mỗi tần số khác 0, hãy thêm (freq [i]) * (freq [i] -1) / 2 để đếm theo điều kiện 1.
-
Bây giờ vì arr_freq [i] khác 0, hãy duyệt qua mọi tần số thay thế.
-
Tính temp_2 dưới dạng arr_freq [(i + j) / 2].
-
Bây giờ nếu temp_2 khác 0 và arr_freq [j] khác 0 thì điều kiện 3 được đáp ứng. Cập nhật số lượng sản phẩm (arr_freq [i] * arr_freq [j]);
-
Sau khi kết thúc tất cả các lần lặp, số đếm sẽ có tổng số các cặp như vậy.
-
Kết quả là số lượt trả lại.
Ví dụ
#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++){
int temp = arr[i];
arr_freq[temp + N]++;
}
for (int i = 0; i < size_2; i++){
if (arr_freq[i] > 0){
int check = (arr_freq[i]) * (arr_freq[i] - 1);
count += check / 2;
for (int j = i + 2; j < 2001; j += 2){
int temp_2 = arr_freq[(i + j) / 2];
if (arr_freq[j] > 0 && temp_2 > 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
Nếu chúng ta chạy đoạn mã trên, nó sẽ tạo ra kết quả sau -
Count of pairs with average present in the same array are: 2