Dada una array arr[] de tamaño N , la tarea para cada elemento de la array arr[i] es contar el número de pares de elementos iguales que se pueden obtener eliminando arr[i] de la array.
Ejemplos:
Entrada: arr[] = { 1, 1, 1, 2 }
Salida: 1 1 1 3
Explicación:
Eliminar arr[0] de la array modifica arr[] a { 1, 1, 2 } y cuenta de pares de elementos iguales = 1
Eliminar arr[1] de la array modifica arr[] a { 1, 1, 2 } y cuenta de pares de elementos iguales = 1
Eliminar arr[2] de la array modifica arr[] a { 1, 1, 2 } y recuento de pares de elementos iguales = 1
Al eliminar arr[3] de la array, se modifica arr[] a { 1, 1, 1 } y recuento de pares de elementos iguales = 3
Por lo tanto, el resultado requerido es 1 1 1 3.Entrada: arr[] = { 2, 3, 4, 3, 2 }
Salida: 1 1 2 1 1
Enfoque ingenuo: el enfoque más simple para resolver este problema es atravesar la array y, por cada i -ésimo elemento, eliminar arr[i] de la array e imprimir el recuento de pares de elementos de array iguales que quedan en la array.
Tiempo Complejidad: O(N 2 )
Espacio auxiliar: O(N)
Enfoque eficiente: siga los pasos a continuación para resolver el problema:
- Inicialice un mapa , digamos mp , para almacenar la frecuencia de cada elemento distinto de la array .
- Inicialice una variable, digamos cntPairs , para almacenar el recuento total de pares de elementos de array iguales.
- Recorra el mapa y almacene el recuento total de pares de elementos iguales incrementando el valor de cntPairs en (mp[i] * (mp[i] – 1)) / 2 .
- Finalmente, recorre la array . Para cada i -ésimo elemento, imprima el valor de (cntPairs – mp[i] + 1) , que denota el recuento de pares de elementos de array iguales al eliminar arr[i] de la array.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to count pairs of equal elements
// by removing arr[i] from the array
void pairs_after_removing(int arr[], int N)
{
// Stores total count of
// pairs of equal elements
int cntPairs = 0;
// Store frequency of each
// distinct array element
unordered_map<int, int> mp;
// Traverse the array
for (int i = 0; i < N; i++) {
// Update frequency of arr[i]
mp[arr[i]]++;
}
// Traverse the map
for (auto element : mp) {
// Stores key of an element
int i = element.first;
cntPairs += mp[i] * (mp[i] - 1) / 2;
}
// Traverse the array
for (int i = 0; i < N; i++) {
// Stores count of pairs of equal
// element by removing arr[i]
int pairs_after_arr_i_removed
= cntPairs + 1 - mp[arr[i]];
cout << pairs_after_arr_i_removed << ' ';
}
return;
}
// Driver Code
int main()
{
// Given Array
int arr[] = { 2, 3, 4, 3, 2 };
int N = sizeof(arr) / sizeof(arr[0]);
pairs_after_removing(arr, N);
return 0;
}
Java
// Java program to implement
// the above approach
import java.util.*;
class GFG{
// Function to count pairs of equal elements
// by removing arr[i] from the array
static void pairs_after_removing(int arr[], int N)
{
// Stores total count of
// pairs of equal elements
int cntPairs = 0;
// Store frequency of each
// distinct array element
Map<Integer,
Integer> mp = new HashMap<Integer,
Integer>();
// Traverse the array
for(int i = 0; i < N; i++)
{
// Update frequency of arr[i]
mp.put(arr[i], mp.getOrDefault(arr[i], 0) + 1);
}
// Traverse the map
for(Map.Entry<Integer,
Integer> element : mp.entrySet())
{
// Stores key of an element
int i = element.getKey();
cntPairs += mp.get(i) * (mp.get(i) - 1) / 2;
}
// Traverse the array
for(int i = 0; i < N; i++)
{
// Stores count of pairs of equal
// element by removing arr[i]
int pairs_after_arr_i_removed = cntPairs +
1 - mp.get(arr[i]);
System.out.print(pairs_after_arr_i_removed + " ");
}
return;
}
// Driver code
public static void main(String[] args)
{
// Given Array
int arr[] = { 2, 3, 4, 3, 2 };
int N = arr.length;
pairs_after_removing(arr, N);
}
}
// This code is contributed by susmitakundugoaldanga
Python3
# python program to implement
# the above approach
# Function to count pairs of equal elements
# by removing arr[i] from the array
def pairs_after_removing(arr, N):
# Stores total count of
# pairs of equal elements
cntPairs = 0
# Store frequency of each
# distinct array element
mp = {}
# Traverse the array
for i in arr:
# Update frequency of arr[i]
mp[i] = mp.get(i, 0) + 1
# Traverse the map
for element in mp:
# Stores key of an element
i = element
cntPairs += mp[i] * (mp[i] - 1) // 2
# Traverse the array
for i in range(N):
# Stores count of pairs of equal
# element by removing arr[i]
pairs_after_arr_i_removed = cntPairs + 1 - mp[arr[i]]
print(pairs_after_arr_i_removed, end = ' ')
return
# Driver Code
if __name__ == '__main__':
# Given Array
arr = [2, 3, 4, 3, 2]
N = len(arr)
pairs_after_removing(arr, N)
# This code is contributed by mohit kumar 29
C#
// C# program to implement
// the above approach
using System;
using System.Collections.Generic;
class GFG
{
// Function to count pairs of equal elements
// by removing arr[i] from the array
static void pairs_after_removing(int[] arr, int N)
{
// Stores total count of
// pairs of equal elements
int cntPairs = 0;
// Store frequency of each
// distinct array element
Dictionary<int,
int> mp = new Dictionary<int,
int>();
// Traverse the array
for(int i = 0; i < N; i++)
{
// Update frequency of arr[i]
if(mp.ContainsKey(arr[i]))
{
mp[arr[i]]++;
}
else
{
mp[arr[i]] = 1;
}
}
// Traverse the map
foreach(KeyValuePair<int,
int> element in mp)
{
// Stores key of an element
int i = element.Key;
cntPairs += mp[i] * (mp[i] - 1) / 2;
}
// Traverse the array
for(int i = 0; i < N; i++)
{
// Stores count of pairs of equal
// element by removing arr[i]
int pairs_after_arr_i_removed = cntPairs +
1 - mp[arr[i]];
Console.Write(pairs_after_arr_i_removed + " ");
}
return;
}
// Driver code
public static void Main()
{
// Given Array
int[] arr = { 2, 3, 4, 3, 2 };
int N = arr.Length;
pairs_after_removing(arr, N);
}
}
// This code is contributed by sanjoy_62
Javascript
<script>
// JavaScript program to implement
// the above approach
// Function to count pairs of equal elements
// by removing arr[i] from the array
function pairs_after_removing(arr, N)
{
// Stores total count of
// pairs of equal elements
var cntPairs = 0;
// Store frequency of each
// distinct array element
var mp = new Map();
// Traverse the array
for (var i = 0; i < N; i++) {
// Update frequency of arr[i]
if(mp.has(arr[i]))
{
mp.set(arr[i], mp.get(arr[i])+1);
}
else
{
mp.set(arr[i], 1);
}
}
// Traverse the map
mp.forEach((value, key) => {
// Stores key of an element
var i = key;
cntPairs += mp.get(i) * (mp.get(i) - 1) / 2;
});
// Traverse the array
for (var i = 0; i < N; i++) {
// Stores count of pairs of equal
// element by removing arr[i]
var pairs_after_arr_i_removed
= cntPairs + 1 - mp.get(arr[i]);
document.write( pairs_after_arr_i_removed + ' ');
}
return;
}
// Driver Code
// Given Array
var arr = [2, 3, 4, 3, 2];
var N = arr.length;
pairs_after_removing(arr, N);
</script>
Producción:
1 1 2 1 1
Complejidad temporal: O(N)
Espacio auxiliar: O(N)