Dada una array arr[] que consta de N enteros, la tarea es contar el número mínimo de veces que se requieren como máximo K elementos iguales para eliminar para que la array quede vacía.
Ejemplos:
Entrada: arr[] = {1, 3, 1, 1, 3}, K = 2
Salida: 3
Explicación:
Paso 1: elimine como máximo 2 1 de la array. La array modificada es {1, 3, 3}.
Paso 2: elimine como máximo 2 3 de la array. La array modificada es {1}.
Paso 3: elimine como máximo 2 1 de la array. La array modificada es {}.
Después de 3 pasos, la array se vacía.
Por lo tanto, el número mínimo de pasos necesarios es de 3.
Entrada : arr[] = {4, 4, 7, 3, 1, 1, 2, 1, 7, 3}, K = 5
Salida : 5
Enfoque ingenuo: el enfoque más simple es atravesar la array y contar la frecuencia de cada elemento de la array y luego dividir la frecuencia de cada elemento por K y agregarla para contar . Incremente el conteo si la frecuencia del elemento de la array no es divisible por K . Después de completar los pasos anteriores, imprima el valor de conteo como resultado.
Complejidad de Tiempo: O(N 2 )
Espacio Auxiliar: O(1)
Enfoque eficiente: Hashing puede optimizar el enfoque anterior para almacenar la frecuencia de cada elemento de la array y luego contar la cantidad mínima de operaciones requeridas. Siga los pasos a continuación para resolver el problema:
- Inicialice una variable, digamos count , que almacene el número mínimo de pasos requeridos.
- Inicialice Hashmap que almacena la frecuencia de cada elemento en la array .
- Recorra la array arr[] y almacene las frecuencias de cada elemento en el Hashmap.
- Recorra el Hashmap y agregue el valor de la frecuencia de cada elemento, dividido por K , a la variable count . Si la frecuencia del elemento de array actual no es divisible por K , incremente la cuenta en 1 .
- Después de completar los pasos anteriores, imprima el conteo como el número mínimo requerido de pasos necesarios para vaciar la array.
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;
// Function to count the minimum
// number of steps required to empty
// given array by removing at most K
// equal array elements in each operation
void minSteps(int arr[], int N, int K)
{
// Stores the minimum number of
// steps required to empty the array
int count = 0;
// Stores the occurrence
// of each array element
map<int, int> cntFreq;
for (int i = 0; i < N; i++)
{
// Update the frequency
cntFreq[arr[i]]++;
}
// Traverse the Hashmap
for (auto i : cntFreq)
{
// Check if the frequency
// is divisible by K or not
if (i.first % K == 0)
count += i.second / K;
// Otherwise
else
count += (i.second / K) + 1;
}
// Print the count of
// minimum steps required
cout << (count);
}
// Driver Code
int main()
{
int arr[] = { 4, 4, 7, 3, 1,
1, 2, 1, 7, 3 };
int N = sizeof(arr) / sizeof(arr[0]);
int K = 5;
minSteps(arr, N, K);
return 0;
}
// This code is contributed by Dharanendra L V.
Java
// Java program for the above approach
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;
class GFG {
// Function to count the minimum
// number of steps required to empty
// given array by removing at most K
// equal array elements in each operation
public static void minSteps(
int[] arr, int N, int K)
{
// Stores the minimum number of
// steps required to empty the array
int count = 0;
// Stores the occurrence
// of each array element
Map<Integer, Integer> cntFreq
= new HashMap<Integer, Integer>();
for (int i = 0; i < N; i++) {
// Update the frequency
cntFreq.put(
arr[i],
cntFreq.getOrDefault(
arr[i], 0)
+ 1);
}
// Traverse the Hashmap
for (Integer i : cntFreq.keySet()) {
// Check if the frequency
// is divisible by K or not
if (cntFreq.get(i) % K == 0)
count += cntFreq.get(i)
/ K;
// Otherwise
else
count += (cntFreq.get(i)
/ K)
+ 1;
}
// Print the count of
// minimum steps required
System.out.print(count);
}
// Driver Code
public static void main(String[] args)
{
int arr[] = { 4, 4, 7, 3, 1,
1, 2, 1, 7, 3 };
int N = arr.length;
int K = 5;
minSteps(arr, N, K);
}
}
Python3
# Python3 program for the above approach
# Function to count the minimum
# number of steps required to empty
# given array by removing at most K
# equal array elements in each operation
def minSteps(arr, N, K) :
# Stores the minimum number of
# steps required to empty the array
count = 0
# Stores the occurrence
# of each array element
cntFreq = {}
for i in range(N) :
# Update the frequency
if arr[i] in cntFreq :
cntFreq[arr[i]] += 1
else :
cntFreq[arr[i]] = 1
# Traverse the Hashmap
for i in cntFreq :
# Check if the frequency
# is divisible by K or not
if (i % K == 0) :
count += cntFreq[i] // K
# Otherwise
else :
count += (cntFreq[i] // K) + 1
# Print the count of
# minimum steps required
print(count)
arr = [ 4, 4, 7, 3, 1, 1, 2, 1, 7, 3 ]
N = len(arr)
K = 5
minSteps(arr, N, K)
# This code is contributed by divyeshabadiya07.
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
public class GFG
{
// Function to count the minimum
// number of steps required to empty
// given array by removing at most K
// equal array elements in each operation
public static void minSteps(
int[] arr, int N, int K)
{
// Stores the minimum number of
// steps required to empty the array
int count = 0;
// Stores the occurrence
// of each array element
Dictionary<int, int> cntFreq
= new Dictionary<int, int>();
for (int i = 0; i < N; i++) {
// Update the frequency
if(cntFreq.ContainsKey(arr[i]))
cntFreq[arr[i]] = cntFreq[arr[i]]+1;
else
cntFreq.Add(arr[i],1);
}
// Traverse the Hashmap
foreach (int i in cntFreq.Keys) {
// Check if the frequency
// is divisible by K or not
if (cntFreq[i] % K == 0)
count += cntFreq[i]
/ K;
// Otherwise
else
count += (cntFreq[i]
/ K)
+ 1;
}
// Print the count of
// minimum steps required
Console.Write(count);
}
// Driver Code
public static void Main(String[] args)
{
int []arr = { 4, 4, 7, 3, 1,
1, 2, 1, 7, 3 };
int N = arr.Length;
int K = 5;
minSteps(arr, N, K);
}
}
// This code is contributed by shikhasingrajput
Javascript
<script>
// JavaScript program for the above approach
// Function to count the minimum
// number of steps required to empty
// given array by removing at most K
// equal array elements in each operation
function minSteps(arr, N, K) {
// Stores the minimum number of
// steps required to empty the array
var count = 0;
// Stores the occurrence
// of each array element
var cntFreq = {};
for (var i = 0; i < N; i++) {
// Update the frequency
if (cntFreq.hasOwnProperty(arr[i]))
cntFreq[arr[i]] += 1;
else
cntFreq[arr[i]] = 1;
}
// Traverse the Hashmap
for (const [key, value] of Object.entries(cntFreq)) {
// Check if the frequency
// is divisible by K or not
if (key % K == 0)
count += parseInt(cntFreq[key] / K);
// Otherwise
else
count += parseInt(cntFreq[key] / K) + 1;
}
// Print the count of
// minimum steps required
document.write(count);
}
// Driver Code
var arr = [4, 4, 7, 3, 1, 1, 2, 1, 7, 3];
var N = arr.length;
var K = 5;
minSteps(arr, N, K);
</script>
5
Complejidad temporal: O(N)
Espacio auxiliar: O(N)