Dada una array arr[] que consta de N enteros, la tarea es encontrar el número mínimo de elementos de la array que deben eliminarse de modo que la diferencia absoluta entre cada par de elementos sea igual.
Ejemplos:
Entrada: arr[] = {1, 2}
Salida: 0
Explicación: Solo hay un par de enteros con diferencia absoluta | array[1] − array[2] | = | 1- 2 | = 1. Por lo tanto, no es necesario eliminar ningún número entero de la array dada.Entrada: arr[] = {2, 5, 1, 2, 2}
Salida: 2
Explicación: Después de eliminar 1 y 5, la array A se convierte en [2, 2, 2] y la diferencia absoluta entre cada par de enteros es 0 .
Enfoque: el problema dado se puede resolver contando las frecuencias de los elementos de la array e imprimir el resultado en función de las siguientes observaciones:
- Si la frecuencia máxima entre todos los elementos de la array es 1 , entonces se deben eliminar todos (N – 2) elementos .
- De lo contrario, el número máximo de elementos de la array que deben eliminarse es (N: frecuencia máxima) , de modo que todos los elementos de la array sean iguales y la diferencia entre dos pares de elementos sea la misma.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
void countToMakeDiffEqual(int arr[], int n)
{
// Stores the element having maximum
// frequency in the array
int ma = 0;
unordered_map<int, int> m;
for (int i = 0; i < n; i++) {
m[arr[i]]++;
// Find the most occurring element
ma = max(ma, m[arr[i]]);
}
// If only one pair exists then the
// absolute difference between them
// will be same
if (n <= 2)
cout << 0 << endl;
else if (ma == 1) {
cout << n - 2 << endl;
}
// Elements to remove is equal to the
// total frequency minus frequency
// of most frequent element
else
cout << n - ma << endl;
}
// Driver Code
int main()
{
int arr[] = { 2, 5, 1, 2, 2 };
int N = sizeof(arr) / sizeof(arr[0]);
countToMakeDiffEqual(arr, N);
return 0;
}
Java
// Java program for the above approach
import java.util.HashMap;
class GFG {
public static void countToMakeDiffEqual(int arr[], int n)
{
// Stores the element having maximum
// frequency in the array
int ma = 0;
HashMap<Integer, Integer> m = new HashMap<Integer, Integer>();
for (int i = 0; i < n; i++) {
// m[arr[i]]++;
if (m.containsKey(arr[i])) {
m.put(arr[i], m.get(arr[i]) + 1);
} else {
m.put(arr[i], 1);
}
// Find the most occurring element
ma = Math.max(ma, m.get(arr[i]));
}
// If only one pair exists then the
// absolute difference between them
// will be same
if (n <= 2)
System.out.println(0);
else if (ma == 1) {
System.out.println(n - 2);
}
// Elements to remove is equal to the
// total frequency minus frequency
// of most frequent element
else
System.out.println(n - ma);
}
// Driver Code
public static void main(String args[]) {
int arr[] = { 2, 5, 1, 2, 2 };
int N = arr.length;
countToMakeDiffEqual(arr, N);
}
}
// This code is contributed by gfgking.
Python3
# Python 3 program for the above approach from collections import defaultdict def countToMakeDiffEqual(arr, n): # Stores the element having maximum # frequency in the array ma = 0 m = defaultdict(int) for i in range(n): m[arr[i]] += 1 # Find the most occurring element ma = max(ma, m[arr[i]]) # If only one pair exists then the # absolute difference between them # will be same if (n <= 2): print(0) elif (ma == 1): print(n - 2) # Elements to remove is equal to the # total frequency minus frequency # of most frequent element else: print(n - ma) # Driver Code if __name__ == "__main__": arr = [2, 5, 1, 2, 2] N = len(arr) countToMakeDiffEqual(arr, N) # This code is contributed by ukasp.
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG{
static void countToMakeDiffEqual(int []arr, int n)
{
// Stores the element having maximum
// frequency in the array
int ma = 0;
Dictionary<int, int> m = new Dictionary<int,int>();
for (int i = 0; i < n; i++) {
if(m.ContainsKey(arr[i]))
m[arr[i]]++;
else
m.Add(arr[i],1);
// Find the most occurring element
ma = Math.Max(ma, m[arr[i]]);
}
// If only one pair exists then the
// absolute difference between them
// will be same
if (n <= 2)
Console.WriteLine(0);
else if (ma == 1) {
Console.WriteLine(n - 2);
}
// Elements to remove is equal to the
// total frequency minus frequency
// of most frequent element
else
Console.WriteLine(n - ma);
}
// Driver Code
public static void Main()
{
int []arr = { 2, 5, 1, 2, 2 };
int N = arr.Length;
countToMakeDiffEqual(arr, N);
}
}
// This code is contributed by ipg2016107.
Javascript
<script>
// JavaScript Program to implement
// the above approach
function countToMakeDiffEqual(arr, n)
{
// Stores the element having maximum
// frequency in the array
let ma = 0;
let m = new Map();
for (let i = 0; i < n; i++) {
if (m.has(arr[i])) {
m.set(arr[i], m.get(arr[i]) + 1);
}
else {
m.set(arr[i], 1);
}
// Find the most occurring element
ma = Math.max(ma, m.get(arr[i]));
}
// If only one pair exists then the
// absolute difference between them
// will be same
if (n <= 2) {
document.write(0 + '<br>');
}
else if (ma == 1) {
document.write(n - 2 + '<br>');
}
// Elements to remove is equal to the
// total frequency minus frequency
// of most frequent element
else {
document.write(n - ma + '<br>');
}
}
// Driver Code
let arr = [2, 5, 1, 2, 2];
let N = arr.length;
countToMakeDiffEqual(arr, N);
// This code is contributed by Potta Lokesh
</script>
Producción:
2
Complejidad temporal: O(N)
Espacio auxiliar: O(1)