Given an array arr[] of size N, the task is to find the number of pairs of the array upon removing which the mean (i.e. the average of all elements) of the array remains unchanged.
Examples:
Input: N = 5, arr[] = {1, 4, 7, 3, 5}
Output: 2
Explanation: The required pairs of positions are – {0, 2} and {3, 4}.
Mean of original array = (1 + 4 + 7 + 3 + 5) / 5 = 4.
On deletion of elements at positions 0 and 2, array becomes {4, 3, 5}.
Mean of the new array = (4 + 3 + 5) / 3 = 4. which is same as the mean of original array.
On deletion of elements at positions 3 and 4, array becomes {1, 4, 7}.
Mean of the new array = (1 + 4 + 7) / 3 = 4. which is same as the mean of original array.Input: N = 3, A = {50, 20, 10}
Output: 0
Explanation: No such pair is possible.
Approach: Consider the below observation:
Observation:
If a sum (S = 2*mean) is subtracted from the original array (with initial mean = M), the mean of the new updated array will still remains as M.
Derivation:
- Sum of array (of size N) = N * mean = N * M
- new mean = (sum of array – 2 * M) / (N – 2)
=(N*M – 2*M)/(N – 2)
= M.
The following steps can be followed to solve the problem –
- Calculate mean of the given array.
- Calculate required sum S i.e. 2*mean.
- If S is not an integer, return 0, since there will not be any pair with a nonintegral sum.
- Else, find a number of required pairs by hashing.
Below is the implementation of the above approach:
C++
// C++ code to implement the above approach#include <bits/stdc++.h>using namespace std;// Function to calculate the number// of pairs of positions [i, j] (i<j),// such that on deletion of elements// at these positions, the mean of// remaining (n-2) elements does not changeint countPairs(int n, int A[]){ // Calculating sum of array int sum = 0; for (int i = 0; i < n; i++) { sum += A[i]; } // Calculating mean of array double mean = (sum * 1.0) / n; // Required sum = twice of mean double required_sum = 2.0 * mean; // Checking if required_sum is integral int check = required_sum; double temp = required_sum - check; if (temp > 0) { return 0; } else { // Initialising count variable to // store total number of valid pairs int count = 0; // Declaring a map to calculate // number of pairs with required sum map<int, int> mp; // Standard procedure to calculate // total number of pairs // of required sum for (int i = 0; i < n; i++) { if (i > 0) { count += mp[required_sum - A[i]]; } mp[A[i]]++; } // Returning count return count; } // If no pairs with required sum return 0;}// Driver codeint main(){ int N = 5; int arr[] = { 1, 4, 7, 3, 5 }; int numberOfPairs = countPairs(N, arr); cout << numberOfPairs; return 0;} |
Java
// Java code to implement the approachimport java.io.*;import java.util.*;class GFG{ // Function to calculate the number // of pairs of positions [i, j] (i<j), // such that on deletion of elements // at these positions, the mean of // remaining (n-2) elements does not change public static int countPairs(int n, int A[]) { // Calculating sum of array int sum = 0; for (int i = 0; i < n; i++) { sum += A[i]; } // Calculating mean of array double mean = (sum * 1.0) / n; // Required sum = twice of mean double required_sum = 2.0 * mean; // Checking if required_sum is integral int check = (int)required_sum; double temp = required_sum - check; if (temp > 0) { return 0; } else { // Initialising count variable to // store total number of valid pairs int count = 0; // Declaring a map to calculate // number of pairs with required sum TreeMap<Integer, Integer> mp = new TreeMap<Integer, Integer>(); // Standard procedure to calculate // total number of pairs // of required sum for (int i = 0; i < n; i++) { if (i > 0) { if (mp.get((int)required_sum - A[i]) != null) { count += mp.get((int)required_sum - A[i]); } } if (mp.get(A[i]) != null) { mp.put(A[i],mp.get(A[i])+1); } else { mp.put(A[i],1); } } // Returning count return count; } } public static void main(String[] args) { int N = 5; int arr[] = { 1, 4, 7, 3, 5 }; int numberOfPairs = countPairs(N, arr); System.out.print(numberOfPairs); }}// This code is contributed by Pushpesh Raj |
Python
# Python code to implement the above approach# Function to calculate the number# of pairs of positions [i, j] (i<j),# such that on deletion of elements# at these positions, the mean of# remaining (n-2) elements does not changedef countPairs(n, A): # Calculating sum of array sum = 0 for i in range(0, n): sum += A[i] # Calculating mean of array mean = (sum * 1.0) / n # Required sum = twice of mean required_sum = 2.0 * mean # Checking if required_sum is integral check = required_sum temp = required_sum - check if (temp > 0): return 0 else: # Initialising count variable to # store total number of valid pairs count = 0 # Declaring a map to calculate # number of pairs with required sum mp = {} # Standard procedure to calculate # total number of pairs # of required sum for i in range(0, n): if (i > 0 and required_sum - A[i] in mp): count += mp[required_sum - A[i]] if arr[i] in mp: mp[arr[i]] += 1 else: mp[arr[i]] = 1 # Returning count return count # If no pairs with required sum return 0# Driver codeN = 5arr = [ 1, 4, 7, 3, 5 ]numberOfPairs = countPairs(N, arr)print(numberOfPairs)# This code is contributed by Samim Hossain Mondal. |
C#
// C# program to implement// the above approachusing System;using System.Collections.Generic;class GFG{ // Function to calculate the number // of pairs of positions [i, j] (i<j), // such that on deletion of elements // at these positions, the mean of // remaining (n-2) elements does not change static int countPairs(int n, int[] A) { // Calculating sum of array int sum = 0; for (int i = 0; i < n; i++) { sum += A[i]; } // Calculating mean of array double mean = (sum * 1.0) / n; // Required sum = twice of mean double required_sum = 2.0 * mean; // Checking if required_sum is integral int check = (int)required_sum; double temp = required_sum - check; if (temp > 0) { return 0; } else { // Initialising count variable to // store total number of valid pairs int count = 0; // Declaring a map to calculate // number of pairs with required sum Dictionary<int, int> mp = new Dictionary<int, int>(); // Standard procedure to calculate // total number of pairs // of required sum for (int i = 0; i < n; i++) { if (i > 0 && ( mp.ContainsKey((int)required_sum - A[i]))) { count += mp[(int)required_sum - A[i]]; } if (mp.ContainsKey(A[i])) { int x = mp[A[i]]; mp[A[i]]= x + 1; } else mp.Add(A[i], 1); } // Returning count return count; } // If no pairs with required sum return 0; } // Driver Code public static void Main() { int N = 5; int[] arr = { 1, 4, 7, 3, 5 }; int numberOfPairs = countPairs(N, arr); Console.Write(numberOfPairs); }}// This code is contributed by sanjoy_62. |
Javascript
<script> // JavaScript code to implement the above approach // Function to calculate the number // of pairs of positions [i, j] (i<j), // such that on deletion of elements // at these positions, the mean of // remaining (n-2) elements does not change const countPairs = (n, A) => { // Calculating sum of array let sum = 0; for (let i = 0; i < n; i++) { sum += A[i]; } // Calculating mean of array let mean = (sum * 1.0) / n; // Required sum = twice of mean let required_sum = 2.0 * mean; // Checking if required_sum is integral let check = required_sum; let temp = required_sum - check; if (temp > 0) { return 0; } else { // Initialising count variable to // store total number of valid pairs let count = 0; // Declaring a map to calculate // number of pairs with required sum let mp = {}; // Standard procedure to calculate // total number of pairs // of required sum for (let i = 0; i < n; i++) { if (i > 0 && (required_sum - A[i] in mp)) { count += mp[required_sum - A[i]]; } if (A[i] in mp) mp[A[i]] += 1; else mp[A[i]] = 1; } // Returning count return count; } // If no pairs with required sum return 0; } // Driver code let N = 5; let arr = [1, 4, 7, 3, 5]; let numberOfPairs = countPairs(N, arr); document.write(numberOfPairs); // This code is contributed by rakeshsahni</script> |
Output
2
Time Complexity: O(N)
Auxiliary Space: O(N)
Share your thoughts in the comments
