Dadas dos arrays arr[] y brr[] de tamaño N y M respectivamente, la tarea es contar el número máximo de elementos que se pueden eliminar de la array arr[] de modo que la suma de elementos en arr[] sea mayor que o igual a la suma de elementos en brr[] .
Ejemplos:
Entrada: arr[] = { 1, 2, 4, 6 }, brr[] = { 7 }
Salida: 2
Explicación:
Eliminar arr[2] modifica arr[] a { 1, 2, 6 } y suma igual a 9 (> 7)
Eliminar arr[1] modifica arr[] a { 1, 6 } y suma igual a 7 (&gr; 7)
Eliminar arr[0] modifica arr[] a { 6 } y suma igual a 6 (< 7 )
Por lo tanto, la salida requerida es 2.Entrada: arr[] = { 10, 20 }, brr[] = { 5 }
Salida: 1
Explicación:
Eliminar arr[1] modifica arr[] a { 10 } y suma igual a 10 (> 5)
Eliminar arr[0 ] modifica arr[] a { } y suma igual a 0 (< 5)
Por lo tanto, la salida requerida es 1.
Enfoque: El problema se puede resolver usando la técnica Greedy . Siga los pasos a continuación para resolver el problema:
- Ordene la array, arr[] en orden ascendente .
- Elimine el elemento más pequeño de la array arr[] y verifique si la suma de los elementos de arr[] es mayor o igual que la suma de los elementos de la array brr[] o no. Si se encuentra que es cierto, entonces incremente el conteo.
- Finalmente, imprima el conteo obtenido.
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 maximize the count of elements
// required to be removed from arr[] such that
// the sum of arr[] is greater than or equal
// to sum of the array brr[]
int maxCntRemovedfromArray(int arr[], int N,
int brr[], int M)
{
// Sort the array arr[]
sort(arr, arr + N);
// Stores index of smallest
// element of arr[]
int i = 0;
// Stores sum of elements
// of the array arr[]
int sumArr = 0;
// Traverse the array arr[]
for (int i = 0; i < N; i++) {
// Update sumArr
sumArr += arr[i];
}
// Stores sum of elements
// of the array brr[]
int sumBrr = 0;
// Traverse the array brr[]
for (int i = 0; i < M; i++) {
// Update sumArr
sumBrr += brr[i];
}
// Stores count of
// removed elements
int cntRemElem = 0;
// Repeatedly remove the smallest
// element of arr[]
while (i < N and sumArr >= sumBrr) {
// Update sumArr
sumArr -= arr[i];
// Remove the smallest element
i += 1;
// If the sum of remaining elements
// in arr[] >= sum of brr[]
if (sumArr >= sumBrr) {
// Update cntRemElem
cntRemElem += 1;
}
}
return cntRemElem;
}
// Driver Code
int main()
{
int arr[] = { 1, 2, 4, 6 };
int brr[] = { 7 };
int N = sizeof(arr) / sizeof(arr[0]);
int M = sizeof(brr) / sizeof(brr[0]);
cout << maxCntRemovedfromArray(arr, N, brr, M);
}
Java
// Java program to implement
// the above approach
import java.io.*;
import java.util.*;
class GFG
{
// Function to maximize the count of elements
// required to be removed from arr[] such that
// the sum of arr[] is greater than or equal
// to sum of the array brr[]
static int maxCntRemovedfromArray(int[] arr, int N,
int[] brr, int M)
{
// Sort the array arr[]
Arrays.sort(arr);
// Stores index of smallest
// element of arr[]
int i = 0;
// Stores sum of elements
// of the array arr[]
int sumArr = 0;
// Traverse the array arr[]
for (i = 0; i < N; i++)
{
// Update sumArr
sumArr += arr[i];
}
// Stores sum of elements
// of the array brr[]
int sumBrr = 0;
// Traverse the array brr[]
for (i = 0; i < M; i++)
{
// Update sumArr
sumBrr += brr[i];
}
// Stores count of
// removed elements
int cntRemElem = 0;
// Repeatedly remove the smallest
// element of arr[]
while (i < N && sumArr >= sumBrr) {
// Update sumArr
sumArr -= arr[i];
// Remove the smallest element
i += 1;
// If the sum of remaining elements
// in arr[] >= sum of brr[]
if (sumArr >= sumBrr) {
// Update cntRemElem
cntRemElem += 1;
}
}
return cntRemElem;
}
// Driver Code
public static void main(String[] args)
{
int[] arr = new int[] { 1, 2, 4, 6 };
int[] brr = new int[] { 7 };
int N = arr.length;
int M = brr.length;
System.out.println(
maxCntRemovedfromArray(arr, N, brr, M));
}
}
// This code is contributed by Dharanendra L V
Python3
# Python3 program to implement # the above approach # Function to maximize the count of elements # required to be removed from arr[] such that # the sum of arr[] is greater than or equal # to sum of the array brr[] def maxCntRemovedfromArray(arr, N, brr, M): # Sort the array arr[] arr.sort(reverse = False) # Stores index of smallest # element of arr[] i = 0 # Stores sum of elements # of the array arr[] sumArr = 0 # Traverse the array arr[] for i in range(N): # Update sumArr sumArr += arr[i] # Stores sum of elements # of the array brr[] sumBrr = 0 # Traverse the array brr[] for i in range(M): # Update sumArr sumBrr += brr[i] # Stores count of # removed elements cntRemElem = 0 # Repeatedly remove the smallest # element of arr[] while (i < N and sumArr >= sumBrr): # Update sumArr sumArr -= arr[i] # Remove the smallest element i += 1 # If the sum of remaining elements # in arr[] >= sum of brr[] if (sumArr >= sumBrr): # Update cntRemElem cntRemElem += 1 return cntRemElem # Driver Code if __name__ == '__main__': arr = [ 1, 2, 4, 6 ] brr = [7] N = len(arr) M = len(brr) print(maxCntRemovedfromArray(arr, N, brr, M)) # This code is contributed by SURENDRA_GANGWAR
C#
// C# program to implement
// the above approach
using System;
class GFG
{
// Function to maximize the count of elements
// required to be removed from arr[] such that
// the sum of arr[] is greater than or equal
// to sum of the array brr[]
static int maxCntRemovedfromArray(int[] arr, int N,
int[] brr, int M)
{
// Sort the array arr[]
Array.Sort(arr);
// Stores index of smallest
// element of arr[]
int i = 0;
// Stores sum of elements
// of the array arr[]
int sumArr = 0;
// Traverse the array arr[]
for (i = 0; i < N; i++)
{
// Update sumArr
sumArr += arr[i];
}
// Stores sum of elements
// of the array brr[]
int sumBrr = 0;
// Traverse the array brr[]
for (i = 0; i < M; i++)
{
// Update sumArr
sumBrr += brr[i];
}
// Stores count of
// removed elements
int cntRemElem = 0;
// Repeatedly remove the smallest
// element of arr[]
while (i < N && sumArr >= sumBrr)
{
// Update sumArr
sumArr -= arr[i];
// Remove the smallest element
i += 1;
// If the sum of remaining elements
// in arr[] >= sum of brr[]
if (sumArr >= sumBrr)
{
// Update cntRemElem
cntRemElem += 1;
}
}
return cntRemElem;
}
// Driver Code
static public void Main()
{
int[] arr = new int[] { 1, 2, 4, 6 };
int[] brr = new int[] { 7 };
int N = arr.Length;
int M = brr.Length;
Console.WriteLine(
maxCntRemovedfromArray(arr, N, brr, M));
}
}
// This code is contributed by Dharanendra L V
Javascript
<script>
// Javascript program of the above approach
// Function to maximize the count of elements
// required to be removed from arr[] such that
// the sum of arr[] is greater than or equal
// to sum of the array brr[]
function maxCntRemovedfromArray(arr, N, brr, M)
{
// Sort the array arr[]
arr.sort();
// Stores index of smallest
// element of arr[]
let i = 0;
// Stores sum of elements
// of the array arr[]
let sumArr = 0;
// Traverse the array arr[]
for (i = 0; i < N; i++)
{
// Update sumArr
sumArr += arr[i];
}
// Stores sum of elements
// of the array brr[]
let sumBrr = 0;
// Traverse the array brr[]
for (i = 0; i < M; i++)
{
// Update sumArr
sumBrr += brr[i];
}
// Stores count of
// removed elements
let cntRemElem = 0;
// Repeatedly remove the smallest
// element of arr[]
while (i < N && sumArr >= sumBrr) {
// Update sumArr
sumArr -= arr[i];
// Remove the smallest element
i += 1;
// If the sum of remaining elements
// in arr[] >= sum of brr[]
if (sumArr >= sumBrr) {
// Update cntRemElem
cntRemElem += 1;
}
}
return cntRemElem;
}
// Driver Code
let arr = [ 1, 2, 4, 6 ];
let brr = [ 7 ];
let N = arr.length;
let M = brr.length;
document.write(
maxCntRemovedfromArray(arr, N, brr, M)
);
</script>
Producción:
2
Complejidad de tiempo: O(N * log(N))
Espacio auxiliar: O(1)