Dado que hay N elementos en una array. La tarea es eliminar elementos de la array de izquierda a derecha. Sin embargo, se requiere algo de tiempo para eliminar un elemento de la array (llamémoslo tiempo de eliminación ). El tiempo para eliminar un elemento es igual al valor de ese elemento en segundos.
Un elemento solo se puede eliminar cuando el tiempo requerido para eliminarlo (tiempo de eliminación) es mayor o igual al tiempo que espera en la array.
Nota : está permitido cambiar el orden de los elementos en la array antes de comenzar a eliminar elementos. Su tarea es encontrar el número máximo de elementos que se pueden eliminar de la array.
Ejemplos:
Entrada : arr[] = {6, 5, 11, 3}
Salida : 3
Explicación : Reordenemos los elementos de la siguiente manera:
3, 5, 6, 11
-El primer elemento tarda 3 segundos en eliminarse. Dado que es el primer elemento, se puede eliminar en 3 segundos.
-El segundo elemento espera 3 segundos en la array. Este elemento tarda 5 segundos en eliminarse, que es más que el tiempo de espera, por lo tanto, puede eliminarse.
-El tercer elemento espera 8 segundos en el arreglo. Este elemento tarda 6 segundos en eliminarse, que es menos que su tiempo de espera, por lo tanto, no se puede eliminar y se omite.
-El cuarto elemento también espera 8 segundos en la array. Este elemento tarda 11 segundos en eliminarse, que es más que el tiempo de espera, por lo tanto, puede eliminarse.
-Por lo tanto, se pueden eliminar un máximo de 3 elementos.Entrada : arr[] = {5, 4, 1, 10}
Salida : 4
Explicación : Reordenemos los elementos de la siguiente forma:
1, 4, 5, 10
Se puede observar que todos ellos pueden ser removidos ya que cada el tiempo de retiro del elemento es mayor o igual a su tiempo de espera.
La idea es ordenar todos los elementos en orden ascendente de su tiempo de remoción. Comience a iterar desde el lado izquierdo y mantenga una suma acumulada del tiempo de eliminación (que servirá como tiempo de espera para el siguiente elemento). Verifique en cada elemento, si su tiempo de remoción es mayor o igual al tiempo acumulado (es el tiempo de espera). Si es menor, entonces no se puede quitar. Si es igual o mayor, se puede eliminar y agregar su tiempo de eliminación en suma acumulativa. Continúe hasta el final de la array.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ code to find the maximum number of
// elements that can be removed
#include <bits/stdc++.h>
using namespace std;
// Function to find maximum number of
// elements that can be removed
int maxRemoval(int arr[], int n)
{
// it will contain frequency of
// elements that can be removed
int count = 0;
// maintain cumulative sum of removal time
int cumulative_sum = 0;
// arrange elements in ascending order
// of their removal time
sort(arr, arr + n);
for (int i = 0; i < n; i++) {
if (arr[i] >= cumulative_sum) {
count++;
cumulative_sum += arr[i];
}
}
return count;
}
// Driver code
int main()
{
int arr[] = { 10, 5, 3, 7, 2 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << maxRemoval(arr, n);
return 0;
}
Java
// Java code to find the maximum number of
// elements that can be removed
import java.io.*;
import java.util.*;
class GFG {
// Function to find maximum number of
// elements that can be removed
static int maxRemoval(int arr[], int n)
{
// it will contain frequency of
// elements that can be removed
int count = 0;
// maintain cumulative sum of removal time
int cumulative_sum = 0;
// arrange elements in ascending order
// of their removal time
Arrays.sort(arr);
for (int i = 0; i < n; i++) {
if (arr[i] >= cumulative_sum) {
count++;
cumulative_sum += arr[i];
}
}
return count;
}
// Driver code
public static void main (String[] args) {
int arr[] = { 10, 5, 3, 7, 2 };
int n = arr.length;
System.out.println(maxRemoval(arr, n));
}
}
// This code is contributed
// by inder_verma..
Python3
# Python3 code to find the maximum number # of elements that can be removed # Function to find maximum number of # elements that can be removed def maxRemoval(arr, n): # It will contain frequency of # elements that can be removed count = 0 # maintain cumulative sum of # removal time cumulative_sum = 0 # arrange elements in ascending # order of their removal time arr.sort() for i in range(n): if arr[i] >= cumulative_sum: count += 1 cumulative_sum += arr[i] return count # Driver code if __name__ == "__main__": arr = [10, 5, 3, 7, 2] n = len(arr) print(maxRemoval(arr, n)) # This code is contributed by # Rituraj Jain
C#
// C# code to find the maximum number
// of elements that can be removed
using System;
class GFG
{
// Function to find maximum number
// of elements that can be removed
static int maxRemoval(int[] arr, int n)
{
// it will contain frequency of
// elements that can be removed
int count = 0;
// maintain cumulative sum
// of removal time
int cumulative_sum = 0;
// arrange elements in ascending
// order of their removal time
Array.Sort(arr);
for (int i = 0; i < n; i++)
{
if (arr[i] >= cumulative_sum)
{
count++;
cumulative_sum += arr[i];
}
}
return count;
}
// Driver code
public static void Main ()
{
int[] arr = { 10, 5, 3, 7, 2 };
int n = arr.Length;
Console.Write(maxRemoval(arr, n));
}
}
// This code is contributed
// by ChitraNayal
PHP
<?php
// PHP code to find the maximum
// number of elements that can
// be removed
// Function to find maximum number
// of elements that can be removed
function maxRemoval(&$arr, $n)
{
// it will contain frequency of
// elements that can be removed
$count = 0;
// maintain cumulative
// sum of removal time
$cumulative_sum = 0;
// arrange elements in ascending
// order of their removal time
sort($arr);
for ($i = 0; $i < $n; $i++)
{
if ($arr[$i] >= $cumulative_sum)
{
$count++;
$cumulative_sum += $arr[$i];
}
}
return $count;
}
// Driver code
$arr = array(10, 5, 3, 7, 2 );
$n = sizeof($arr);
echo (maxRemoval($arr, $n));
// This code is contributed
// by Shivi_Aggarwal
?>
Javascript
<script>
// Javascript code to find the maximum number of
// elements that can be removed
// Function to find maximum number of
// elements that can be removed
function maxRemoval(arr, n)
{
// it will contain frequency of
// elements that can be removed
var count = 0;
// maintain cumulative sum of removal time
var cumulative_sum = 0;
// arrange elements in ascending order
// of their removal time
arr.sort((a,b)=> a-b);
for (var i = 0; i < n; i++) {
if (arr[i] >= cumulative_sum) {
count++;
cumulative_sum += arr[i];
}
}
return count;
}
// Driver code
var arr = [ 10, 5, 3, 7, 2 ];
var n = arr.length;
document.write( maxRemoval(arr, n));
</script>
4
Complejidad de tiempo: O(nlogn)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por Shashank_Sharma y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA