Recuento de pares que se pueden eliminar de Array sin cambiar la media

arr[] N ,

Ejemplos:

Entrada: N = 5, arr[] = {1, 4, 7, 3, 5}
Salida:  2
Explicación : los pares de posiciones requeridos son: {0, 2} y {3, 4}.
Media de la array original = (1 + 4 + 7 + 3 + 5) / 5 = 4.
Al eliminar los elementos en las posiciones 0 y 2, la array se convierte en {4, 3, 5}. 
Media de la nueva array = (4 + 3 + 5) / 3 = 4, que es igual a la media de la array original.
Al eliminar elementos en las posiciones 3 y 4, la array se convierte en {1, 4, 7}. 
Media de la nueva array = (1 + 4 + 7) / 3 = 4, que es igual a la media de la array original.

Entrada: N = 3, A = {50, 20, 10}
Salida: 0
Explicación: No es posible tal par.

Enfoque: Considere la siguiente observación:

Observación:

Si se resta una suma (S = 2*media) de la array original (con media inicial = M), la media de la nueva array actualizada seguirá siendo M.

Derivación:

• Suma de array (de tamaño N) = N * media = N * M
• nueva media = (suma de la array – 2 * M) / (N – 2)
                    =(N*M – 2*M) / (N – 2)
                    = M.

Se pueden seguir los siguientes pasos para resolver el problema: 

• Calcular la media de la array dada.
• Calcule la suma requerida S , es decir , 2*media .
• Si S no es un número entero, devuelve 0 , ya que no habrá ningún par con una suma no integral.
• De lo contrario, encuentre una cantidad de pares requeridos mediante hash .

A continuación se muestra la implementación del enfoque anterior:

// 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 change
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 = 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 code
int main()
{
    int N = 5;
    int arr[] = { 1, 4, 7, 3, 5 };
    int numberOfPairs = countPairs(N, arr);
    cout << numberOfPairs;
    return 0;
}

// Java code to implement the approach
import 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 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
def 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 code
 
N = 5
arr = [ 1, 4, 7, 3, 5 ]
numberOfPairs = countPairs(N, arr)
print(numberOfPairs)
 
# This code is contributed by Samim Hossain Mondal.

// C# program to implement
// the above approach
using 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.

<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>

2

Tiempo Complejidad : O(N)
Espacio Auxiliar : O(N)