Dada una array arr[] de tamaño N . En cada operación, elija un elemento de array X y elimine todos los elementos de array en el rango [X – 1, X + 1] . La tarea es encontrar el número máximo de pasos necesarios para que no queden monedas en la array.
Ejemplos:
Entrada: monedas [] = {5, 1, 3, 2, 6, 7, 4}
Salida: 4
Explicación:
Al elegir la moneda monedas [1], se modifica la array arr[] = {5, 3, 6, 7, 4 }.
Escoger la moneda monedas[1] modifica el arreglo arr[] = {5, 6, 7}
Escoger la moneda monedas[0] modifica el arreglo arr[] = {7}
Escoger la moneda monedas[0] modifica el arreglo arr[ ] = {}. Por lo tanto, la salida requerida es 4.Entrada: monedas [] = {6, 7, 5, 1}
Salida: 3
Enfoque ingenuo: el enfoque más simple para resolver este problema es generar todas las permutaciones posibles de la array dada y, para cada permutación de la array, encontrar la cantidad de pasos necesarios para eliminar todos los elementos de la array seleccionando solo el primer elemento de la array. array en todos los pasos posibles. Finalmente, imprima el número máximo de pasos necesarios para eliminar todos los elementos.
Complejidad temporal: O(N!)
Espacio auxiliar: O(1)
Enfoque eficiente: para optimizar el enfoque anterior, la idea es elegir un elemento de la array de tal manera que en cada paso se eliminen como máximo dos elementos de la array. Siga los pasos a continuación para resolver el problema:
- Inicialice una variable, digamos cntSteps para almacenar la cantidad máxima de pasos necesarios para eliminar todas las monedas de la array arr[] .
- Cree un mapa , diga Mapa para almacenar la frecuencia de los elementos de la array arr[] en orden ascendente.
- Inicialice una variable, diga Min para almacenar el elemento más pequeño del Mapa .
- Recorra el Mapa y en cada recorrido elimine el Min y (Min + 1) del Mapa y también incremente el valor de cntSteps en 1 .
- Finalmente, imprima el valor de cntSteps .
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 find maximum steps to
// remove all coins from the arr[]
int maximumSteps(int arr[], int N)
{
// Store the frequency of array
// elements in ascending order
map<int, int> Map;
// Traverse the arr[] array
for (int i = 0; i < N; i++) {
Map[arr[i]]++;
}
// Stores count of steps required
// to remove all the array elements
int cntSteps = 0;
// Traverse the map
for (auto i : Map) {
// Stores the smallest element
// of Map
int X = i.first;
// If frequency if X
// greater than 0
if (i.second > 0) {
// Update cntSteps
cntSteps++;
// Mark X as
// removed element
Map[X] = 0;
// If frequency of (X + 1)
// greater than 0
if (Map[X + 1])
// Mark (X + 1) as
// removed element
Map[X + 1] = 0;
}
}
return cntSteps;
}
// Driver Code
int main()
{
int arr[] = { 5, 1, 3, 2, 6, 7, 4 };
int N = sizeof(arr) / sizeof(arr[0]);
cout << maximumSteps(arr, N);
return 0;
}
Java
// Java program to implement
// the above approach
import java.util.*;
class GFG{
// Function to find maximum steps to
// remove all coins from the arr[]
static int maximumSteps(int arr[], int N)
{
// Store the frequency of array
// elements in ascending order
Map<Integer,
Integer> mp = new HashMap<Integer,
Integer>();
// Traverse the arr[] array
for(int i = 0; i < N; i++)
{
mp.put(arr[i],
mp.getOrDefault(arr[i], 0) + 1);
}
// Stores count of steps required
// to remove all the array elements
int cntSteps = 0;
// Traverse the mp
for(Map.Entry<Integer, Integer> it : mp.entrySet())
{
// Stores the smallest element
// of mp
int X = it.getKey();
// If frequency if X
// greater than 0
if (it.getValue() > 0)
{
// Update cntSteps
cntSteps++;
// Mark X as
// removed element
mp.replace(X, 0);
// If frequency of (X + 1)
// greater than 0
if (mp.getOrDefault(X + 1, 0) != 0)
// Mark (X + 1) as
// removed element
mp.replace(X + 1, 0);
}
}
return cntSteps;
}
// Driver Code
public static void main(String args[])
{
int arr[] = { 5, 1, 3, 2, 6, 7, 4 };
int N = arr.length;
System.out.print(maximumSteps(arr, N));
}
}
// This code is contributed by ipg2016107
Python3
# Python3 program to implement
# the above approach
# Function to find maximum steps to
# remove all coins from the arr[]
def maximumSteps(arr, N):
# Store the frequency of array
# elements in ascending order
Map = {}
# Traverse the arr[] array
for i in range(N):
Map[arr[i]] = Map.get(arr[i], 0) + 1
# Stores count of steps required
# to remove all the array elements
cntSteps = 0
# Traverse the map
for i in Map:
# Stores the smallest element
# of Map
X = i
# If frequency if X
# greater than 0
if (Map[i] > 0):
# Update cntSteps
cntSteps += 1
# Mark X as
# removed element
Map[X] = 0
# If frequency of (X + 1)
# greater than 0
if (X + 1 in Map):
# Mark (X + 1) as
# removed element
Map[X + 1] = 0
return cntSteps
# Driver Code
if __name__ == '__main__':
arr = [ 5, 1, 3, 2, 6, 7, 4 ]
N = len(arr)
print(maximumSteps(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 find maximum steps to
// remove all coins from the []arr
static int maximumSteps(int []arr, int N)
{
// Store the frequency of array
// elements in ascending order
Dictionary<int,
int> mp = new Dictionary<int,
int>();
// Traverse the []arr array
for(int i = 0; i < N; i++)
{
if (mp.ContainsKey(arr[i]))
{
mp[arr[i]]++;
}
else
{
mp.Add(arr[i], 1);
}
}
// Stores count of steps required
// to remove all the array elements
int cntSteps = 0;
// Traverse the mp
foreach(KeyValuePair<int, int> it in mp)
{
// Stores the smallest element
// of mp
int X = it.Key;
// If frequency if X
// greater than 0
if (it.Value > 0)
{
// Update cntSteps
cntSteps++;
}
}
return (cntSteps + 1) / 2;
}
// Driver Code
public static void Main(String []args)
{
int []arr = { 5, 1, 3, 2, 6, 7, 4 };
int N = arr.Length;
Console.Write(maximumSteps(arr, N));
}
}
// This code is contributed by Princi Singh
Javascript
<script>
// Javascript program to implement
// the above approach
// Function to find maximum steps to
// remove all coins from the arr[]
function maximumSteps(arr, N)
{
// Store the frequency of array
// elements in ascending order
var map = new Map();
// Traverse the arr[] array
for (var i = 0; i < N; i++) {
if(map.has(arr[i]))
{
map.set(arr[i], map.get(arr[i])+1);
}
else
{
map.set(arr[i], 1);
}
}
// Stores count of steps required
// to remove all the array elements
var cntSteps = 0;
// Traverse the map
map.forEach((value, key) => {
// Stores the smallest element
// of map
var X = key;
// If frequency if X
// greater than 0
if (value > 0) {
// Update cntSteps
cntSteps++;
// Mark X as
// removed element
map.set(X, 0);
// If frequency of (X + 1)
// greater than 0
if (map.has(X + 1))
// Mark (X + 1) as
// removed element
map.set(X+1, 0);
}
});
return cntSteps;
}
// Driver Code
var arr = [5, 1, 3, 2, 6, 7, 4];
var N = arr.length;
document.write( maximumSteps(arr, N));
</script>
4
Complejidad de tiempo: O(N * Log(N))
Complejidad de espacio: O(N)
Publicación traducida automáticamente
Artículo escrito por promaroy20 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA