- Trending Categories
- Data Structure
- Networking
- RDBMS
- Operating System
- Java
- iOS
- HTML
- CSS
- Android
- Python
- C Programming
- C++
- C#
- MongoDB
- MySQL
- Javascript
- PHP

- Selected Reading
- UPSC IAS Exams Notes
- Developer's Best Practices
- Questions and Answers
- Effective Resume Writing
- HR Interview Questions
- Computer Glossary
- Who is Who

We are given an array of integers such that each element of the array is in the range [- 1000,1000]. The goal is to find pairs of elements of the array such that their average is also present in that array. If array is arr[]= [1,2,3,4]. Then pairs would be (1,3) and (2,4) as the average of 1,3 is 2 and the average of 2,4 is 3 and both 2 and 3 are present in the array. Count would be 2.

Let us understand with examples.

**Input** − arr[]= { -1,2,5,-3,8,10 }

**Output** − Count of pairs with average present in the same array are − 2

**Explanation** − Pairs such that their average is present in arr[] are − (-1,5) avg is 2, (2,8) avg is 5. Count=2

**Input** − arr[] = {1,3,2,5,10,6}

**Output** − Count of pairs with an average present in the same array are − 3

**Explanation** − Pairs such that their average is present in arr[] are − (1,3) avg is 2, (1,5) avg is 3, (2,10) avg is 6. Count=3.

We will first make a frequency array for all elements of the array. The size of the frequency array is double the size of the original array as there could be negative elements as well.

Frequency of negative numbers will start from index 0 to index 1000. And the frequency of positive numbers will start from index 1000 to 2000.

For each non zero frequency do this −

Add (freq[i]) * (freq[i]-1)/2 to count, because the average of two same numbers is the number itself. If there are 5 2’s in the array. Then total pairs would be (5*(5-1))/2=10.

If the above freq[i] is non zero then start traversing for alternate frequencies as consecutive numbers have average which is floating-point and would not be there in the array.

If freq[j] is found which is non-zero and freq[ (i+j)/2 ] is also non-zero. Then add freq[i]*freq[j] to the count( as each number can pair with every other number ).

Take an integer array arr[]

Function average_pair(arr, size) takes the array and its size and returns the count of pairs such that the average of elements in pair is also present in the array arr[].

Take initial count as 0 and initialize N=1000.

Calculate length of frequency array as size_2=2*N+1 ( for range [-1000 to 1000]

Initialize frequency array with 0 initially.

Populate frequency array such that the frequency of negative elements is from 0 to 1000 and positive elements afterward. For this add N to indexes.

For each element arr[i] update frequency array as arr_freq[arr[i] + N]++;

Now traverse the frequency array from i=0 to i<size_2.

For each non-zero frequency add (freq[i]) * (freq[i]-1)/2 to count according to condition 1.

Now as arr_freq[i] is non-zero, traverse every alternate frequency.

Calculate temp_2 as arr_freq[(i + j) / 2].

Now if temp_2 is non-zero and arr_freq[j] is non-zero then condition 3 is met. Update count with product (arr_freq[i] * arr_freq[j]);

After the end of all iterations, the count will have a total number of such pairs.

Return count as result.

#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; }

If we run the above code it will generate the following output −

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

- Related Questions & Answers
- Split Array With Same Average in C++
- Maximum count of pairs which generate the same sum in C++
- Count divisible pairs in an array in C++
- Count the number of sub-arrays such that the average of elements present in the subarray is greater than that not present in the sub-array in C++
- Count pairs with given sum in C++
- Count pairs with Odd XOR in C++
- Count occurrences of the average of array elements with a given number in C++
- Count of index pairs with equal elements in an array in C++
- Count valid pairs in the array satisfying given conditions in C++
- Count pairs whose products exist in array in C++
- Program to count index pairs for which array elements are same in Python
- Count number of subsets whose median is also present in the same subset in C++
- Count all pairs with given XOR in C++
- Count characters with same neighbors in C++
- Splitting array of numbers into two arrays with same average in JavaScript

Advertisements