Cuente los pares de elementos iguales posibles excluyendo cada elemento de la array una vez

Dada una array arr[] de N enteros, la tarea para cada elemento de la array es encontrar el número de formas de elegir un par de dos elementos iguales excluyendo el elemento actual.

Ejemplos:

Entrada: arr[] = {1, 1, 2, 1, 2}
Salida: 2 2 3 2 3
Explicación: 
Para arr[0] (= 1): los elementos restantes de la array son {1, 2, 1, 2} . Las posibles opciones de pares son (1, 1), (2, 2). Por lo tanto, la cuenta es 2.
Para arr[1] (= 1): los elementos restantes de la array son {1, 2, 1, 2}. Por lo tanto, la cuenta es 2.
Para arr[2] (= 2): los elementos restantes de la array son {1, 1, 1, 2}. Las posibles opciones de pares son (arr[0], arr[1]), (arr[1], arr[2]) y (arr[0], arr[2]). Por lo tanto, cuenta es 3.
Para arr[3] (= 1): Los elementos restantes son {1, 1, 2, 2}. Por lo tanto, cuenta es 2.
Para arr[4] (= 2): Los elementos restantes son {1, 1, 2, 1}. Por lo tanto, la cuenta es 3.

Entrada: arr[] = {1, 2, 1, 4, 2, 1, 4, 1}  
Salida: 5 7 5 7 7 5 7 5

Enfoque ingenuo: el enfoque más simple para resolver este problema es recorrer la array para cada elemento de la array, contar todos los pares posibles de elementos iguales de la array restante.

Complejidad de Tiempo: O(N ³ )  
Espacio Auxiliar: O(1)

Enfoque eficiente: el enfoque anterior se puede optimizar en función de la observación de que, para cualquier i ^-ésimo índice (1 ≤ i ≤ N), calcule los dos valores siguientes:

• El número de formas de elegir dos elementos distintos que tienen valores iguales de la array.
• El número de formas de elegir un elemento de los N − 1 elementos de la array que no sea el i ^-ésimo elemento de modo que sus valores sean los mismos que el valor del i ^-ésimo elemento.

Siga los pasos a continuación para resolver el problema:

1. Inicialice un mapa , digamos mp , para almacenar la frecuencia de cada elemento del arreglo .
2. Recorre el mapa para contar el número de pares formados por valores iguales. Almacene el conteo en una variable, digamos total .
3. Recorra la array y para cada i ^-ésimo índice, imprima el total – (mp[arr[i]] – 1) como la respuesta requerida.

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

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to count the number of
// required pairs for every array element
void countEqualElementPairs(int arr[], int N)
{
    // Initialize a map
    unordered_map<int, int> mp;
 
    // Update the frequency
    // of every element
    for (int i = 0; i < N; i++) {
        mp[arr[i]] += 1;
    }
 
    // Stores the count of pairs
    int total = 0;
 
    // Traverse the map
    for (auto i : mp) {
 
        // Count the number of ways to
        // select pairs consisting of
        // equal elements only
        total += (i.second * (i.second - 1)) / 2;
    }
 
    // Traverse the array
    for (int i = 0; i < N; i++) {
 
        // Print the count for
        // every array element
        cout << total - (mp[arr[i]] - 1)
             << " ";
    }
}
 
// Driver code
int main()
{
    // Given array
    int arr[] = { 1, 1, 2, 1, 2 };
 
    // Size of the array
    int N = sizeof(arr) / sizeof(arr[0]);
 
    countEqualElementPairs(arr, N);
}

/*package whatever //do not write package name here */
import java.io.*;
import java.util.Map;
import java.util.HashMap;
 
class GFG
{
   
  // Function to count the number of
  // required pairs for every array element
  public static void countEqualElementPairs(int arr[],
                                            int N)
  {
     
    // Initialize a map
    HashMap<Integer, Integer> map = new HashMap<>();
     
    // Update the frequency
    // of every element
    for (int i = 0; i < N; i++)
    {
      Integer k = map.get(arr[i]);
      map.put(arr[i], (k == null) ? 1 : k + 1);
    }
     
    // Stores the count of pairs
    int total = 0;
 
    // Traverse the map
    for (Map.Entry<Integer, Integer> e :
         map.entrySet())
    {
       
      // Count the number of ways to
      // select pairs consisting of
      // equal elements only
      total
        += (e.getValue() * (e.getValue() - 1)) / 2;
    }
 
    // Traverse the array
    for (int i = 0; i < N; i++) {
 
      // Print the count for
      // every array element
      System.out.print(total - (map.get(arr[i]) - 1)
                       + " ");
    }
  }
 
  // Driver code
  public static void main(String[] args)
  {
     
    // Given array
    int arr[] = { 1, 1, 2, 1, 2 };
 
    // Size of the array
    int N = 5;
 
    countEqualElementPairs(arr, N);
  }
}
 
// This code is contributed by adity7409.

# Python3 program for the above approach
 
# Function to count the number of
# required pairs for every array element
def countEqualElementPairs(arr, N):
   
    # Initialize a map
    mp = {}
 
    # Update the frequency
    # of every element
    for i in range(N):
        if arr[i] in mp:
            mp[arr[i]] += 1
        else:
            mp[arr[i]] = 1
 
    # Stores the count of pairs
    total = 0
 
    # Traverse the map
    for key,value in mp.items():
       
        # Count the number of ways to
        # select pairs consisting of
        # equal elements only
        total += (value * (value - 1)) / 2
 
    # Traverse the array
    for i in range(N):
       
        # Print the count for
        # every array element
        print(int(total - (mp[arr[i]] - 1)),end = " ")
 
# Driver code
if __name__ == '__main__':
   
    # Given array
    arr = [1, 1, 2, 1, 2]
 
    # Size of the array
    N = len(arr)
 
    countEqualElementPairs(arr, N)
     
    # This code is contributed by SURENDRA_GANGWAR.

// C# program for the above approach
using System;
using System.Collections.Generic;
 
class GFG{
 
// Function to count the number of
// required pairs for every array element
static void countEqualElementPairs(int[] arr, int N)
{
 
    // Initialize a map
    Dictionary<int,
               int> map = new Dictionary<int,
                                         int>();
 
    // Update the frequency
    // of every element
    for(int i = 0; i < N; i++)
    {
        if (!map.ContainsKey(arr[i]))
            map[arr[i]] = 1;
        else
            map[arr[i]]++;
    }
 
    // Stores the count of pairs
    int total = 0;
 
    // Traverse the map
    foreach(KeyValuePair<int, int> e in map)
    {
         
        // Count the number of ways to
        // select pairs consisting of
        // equal elements only
        total += (e.Value * (e.Value - 1)) / 2;
    }
 
    // Traverse the array
    for(int i = 0; i < N; i++)
    {
         
        // Print the count for
        // every array element
        Console.Write(total - (map[arr[i]] - 1) + " ");
    }
}
 
// Driver code
public static void Main()
{
     
    // Given array
    int[] arr = { 1, 1, 2, 1, 2 };
 
    // Size of the array
    int N = 5;
 
    countEqualElementPairs(arr, N);
}
}
 
// This code is contributed by ukasp

<script>
 
// Javascript program for the above approach
 
// Function to count the number of
// required pairs for every array element
function countEqualElementPairs(arr, N)
{
     
    // Initialize a map
    var mp = new Map();
 
    // Update the frequency
    // of every element
    for(var i = 0; i < N; i++)
    {
        if (mp.has(arr[i]))
        {
            mp.set(arr[i], mp.get(arr[i]) + 1);
        }
        else
        {
            mp.set(arr[i], 1);
        }
    }
 
    // Stores the count of pairs
    var total = 0;
 
    // Traverse the map
    mp.forEach((value, key) => {
         
        // Count the number of ways to
        // select pairs consisting of
        // equal elements only
        total += (value * (value - 1)) / 2;
    });
 
    // Traverse the array
    for(var i = 0; i < N; i++)
    {
         
        // Print the count for
        // every array element
        document.write(total -
                      (mp.get(arr[i]) - 1) + " ");
    }
}
 
// Driver code
 
// Given array
var arr = [ 1, 1, 2, 1, 2 ];
 
// Size of the array
var N = arr.length;
countEqualElementPairs(arr, N);
 
// This code is contributed by rutvik_56
 
</script>

2 2 3 2 3

Complejidad temporal: O(N)
Espacio auxiliar: O(N)