배열의 각 요소가 [- 1000,1000] 범위에 있도록 정수 배열이 제공됩니다. 목표는 평균이 해당 배열에도 존재하도록 배열의 요소 쌍을 찾는 것입니다. 배열이 arr[]=[1,2,3,4]인 경우. 그러면 1,3의 평균이 2이고 2,4의 평균이 3이고 2와 3이 모두 배열에 있으므로 쌍은 (1,3) 및 (2,4)가 됩니다. 개수는 2입니다.
예를 들어 이해합시다.
입력 - arr[]={ -1,2,5,-3,8,10 }
출력 − 동일한 배열에 평균이 있는 쌍의 수는 − 2
입니다.설명 − arr[]에 평균이 존재하는 쌍은 − (-1,5) avg는 2, (2,8) avg는 5입니다. Count=2
입력 - arr[] ={1,3,2,5,10,6}
출력 − 동일한 배열에 평균이 있는 쌍의 수는 − 3
입니다.설명 − arr[]에 평균이 존재하는 쌍은 − (1,3) avg는 2, (1,5) avg는 3, (2,10) avg는 6입니다. Count=3.
아래 프로그램에서 사용한 접근 방식은 다음과 같습니다.
먼저 배열의 모든 요소에 대한 주파수 배열을 만듭니다. 주파수 배열의 크기는 음수 요소도 있을 수 있으므로 원래 배열의 크기의 두 배입니다.
음수의 빈도는 인덱스 0에서 인덱스 1000까지 시작합니다. 양수의 빈도는 인덱스 1000에서 2000까지 시작됩니다.
0이 아닌 각 주파수에 대해 다음을 수행하십시오. -
-
(freq[i]) * (freq[i]-1)/2를 더하여 계산합니다. 두 개의 동일한 숫자의 평균이 숫자 자체이기 때문입니다. 배열에 5개의 2가 있는 경우. 그러면 총 쌍은 (5*(5-1))/2=10이 됩니다.
-
위의 freq[i]가 0이 아니면 연속 숫자가 부동 소수점이고 배열에 없는 평균을 가지므로 대체 주파수에 대한 탐색을 시작합니다.
-
0이 아닌 freq[j]가 발견되고 freq[ (i+j)/2 ]도 0이 아닌 경우. 그런 다음 freq[i]*freq[j]를 개수에 추가합니다(각 숫자는 다른 모든 숫자와 짝을 이룰 수 있으므로).
-
정수 배열을 취하십시오 arr[]
-
Average_pair(arr, size) 함수는 배열과 배열의 크기를 가져와 쌍의 요소 평균이 배열 arr[]에도 표시되도록 쌍의 개수를 반환합니다.
-
초기 카운트를 0으로 취하고 N=1000을 초기화합니다.
-
size_2=2*N+1(범위 [-1000 ~ 1000]
)으로 주파수 배열의 길이를 계산합니다. -
초기에 0으로 주파수 배열을 초기화합니다.
-
음수 요소의 빈도가 0에서 1000 사이가 되도록 주파수 배열을 채우고 그 이후에 양수 요소를 채웁니다. 이를 위해 인덱스에 N을 추가합니다.
-
각 요소 arr[i]에 대해 arr_freq[arr[i] + N]++;
로 빈도 배열을 업데이트합니다. -
이제 i=0에서 i
-
0이 아닌 각 주파수에 대해 (freq[i]) * (freq[i]-1)/2를 추가하여 조건 1에 따라 계산합니다.
-
이제 arr_freq[i]가 0이 아니므로 모든 대체 주파수를 순회합니다.
-
temp_2를 arr_freq[(i + j) / 2]로 계산합니다.
-
이제 temp_2가 0이 아니고 arr_freq[j]가 0이 아니면 조건 3이 충족됩니다. 제품 업데이트 횟수(arr_freq[i] * arr_freq[j]),
-
모든 반복이 끝나면 카운트는 그러한 쌍의 총 수를 갖게 됩니다.
-
결과로 카운트를 반환합니다.
예시
#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;
} 출력
위의 코드를 실행하면 다음 출력이 생성됩니다 -
Count of pairs with average present in the same array are: 2