Dada una array arr[] que consta de N elementos, la tarea es eliminar la cantidad mínima de elementos de los extremos de la array de modo que la suma total de la array disminuya en al menos K . Tenga en cuenta que K siempre será menor o igual que la suma de todos los elementos de la array.
Ejemplos:
Entrada: arr[] = {1, 11, 5, 5}, K = 11
Salida: 2
Después de eliminar dos elementos del
extremo izquierdo, la suma disminuye en 1 + 11 = 12.
Por lo tanto, la respuesta es 2.
Entrada: array[] = {1, 2, 3}, K = 6
Salida: 3
Enfoque: un enfoque basado en programación dinámica ya se ha discutido en otra publicación. En este artículo, se discutirá un enfoque que utiliza la técnica de dos puntos . Se puede observar que la tarea es encontrar el subarreglo más largo con la suma de sus elementos como máximo sum(arr) – K donde sum(arr) es la suma de todos los elementos del arreglo arr[] .
Sea L la longitud de dicho subarreglo . Por lo tanto, el número mínimo de elementos que se eliminarán de la array será igual a N – L. Para encontrar la longitud del subarreglo más largo, consulte este artículo.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Function to return the count of minimum
// elements to be removed from the ends
// of the array such that the sum of the
// array decrease by at least K
int minCount(int* arr, int n, int k)
{
// To store the final answer
int ans = 0;
// Maximum possible sum required
int sum = 0;
for (int i = 0; i < n; i++)
sum += arr[i];
sum -= k;
// Left point
int l = 0;
// Right pointer
int r = 0;
// Total current sum
int tot = 0;
// Two pointer loop
while (l < n) {
// If the sum fits
if (tot <= sum) {
// Update the answer
ans = max(ans, r - l);
if (r == n)
break;
// Update the total sum
tot += arr[r++];
}
else {
// Increment the left pointer
tot -= arr[l++];
}
}
return (n - ans);
}
// Driver code
int main()
{
int arr[] = { 1, 11, 5, 5 };
int n = sizeof(arr) / sizeof(int);
int k = 11;
cout << minCount(arr, n, k);
return 0;
}
Java
// Java implementation of the approach
class GFG
{
// Function to return the count of minimum
// elements to be removed from the ends
// of the array such that the sum of the
// array decrease by at least K
static int minCount(int arr[],
int n, int k)
{
// To store the final answer
int ans = 0;
// Maximum possible sum required
int sum = 0;
for (int i = 0; i < n; i++)
sum += arr[i];
sum -= k;
// Left point
int l = 0;
// Right pointer
int r = 0;
// Total current sum
int tot = 0;
// Two pointer loop
while (l < n)
{
// If the sum fits
if (tot <= sum)
{
// Update the answer
ans = Math.max(ans, r - l);
if (r == n)
break;
// Update the total sum
tot += arr[r++];
}
else
{
// Increment the left pointer
tot -= arr[l++];
}
}
return (n - ans);
}
// Driver code
public static void main (String[] args)
{
int arr[] = { 1, 11, 5, 5 };
int n = arr.length;
int k = 11;
System.out.println(minCount(arr, n, k));
}
}
// This code is contributed by AnkitRai01
Python3
# Python3 implementation of the approach # Function to return the count of minimum # elements to be removed from the ends # of the array such that the sum of the # array decrease by at least K def minCount(arr, n, k) : # To store the final answer ans = 0; # Maximum possible sum required sum = 0; for i in range(n) : sum += arr[i]; sum -= k; # Left point l = 0; # Right pointer r = 0; # Total current sum tot = 0; # Two pointer loop while (l < n) : # If the sum fits if (tot <= sum) : # Update the answer ans = max(ans, r - l); if (r == n) : break; # Update the total sum tot += arr[r]; r += 1 else : # Increment the left pointer tot -= arr[l]; l += 1 return (n - ans); # Driver code if __name__ == "__main__" : arr = [ 1, 11, 5, 5 ]; n = len(arr); k = 11; print(minCount(arr, n, k)); # This code is contributed by AnkitRai01
C#
// C# implementation of the approach
using System;
class GFG
{
// Function to return the count of minimum
// elements to be removed from the ends
// of the array such that the sum of the
// array decrease by at least K
static int minCount(int []arr,
int n, int k)
{
// To store the final answer
int ans = 0;
// Maximum possible sum required
int sum = 0;
for (int i = 0; i < n; i++)
sum += arr[i];
sum -= k;
// Left point
int l = 0;
// Right pointer
int r = 0;
// Total current sum
int tot = 0;
// Two pointer loop
while (l < n)
{
// If the sum fits
if (tot <= sum)
{
// Update the answer
ans = Math.Max(ans, r - l);
if (r == n)
break;
// Update the total sum
tot += arr[r++];
}
else
{
// Increment the left pointer
tot -= arr[l++];
}
}
return (n - ans);
}
// Driver code
public static void Main()
{
int []arr = { 1, 11, 5, 5 };
int n = arr.Length;
int k = 11;
Console.WriteLine(minCount(arr, n, k));
}
}
// This code is contributed by AnkitRai01
Javascript
<script>
// Javascript implementation of the approach
// Function to return the count of minimum
// elements to be removed from the ends
// of the array such that the sum of the
// array decrease by at least K
function minCount(arr, n, k)
{
// To store the final answer
var ans = 0;
// Maximum possible sum required
var sum = 0;
for (var i = 0; i < n; i++)
sum += arr[i];
sum -= k;
// Left point
var l = 0;
// Right pointer
var r = 0;
// Total current sum
var tot = 0;
// Two pointer loop
while (l < n) {
// If the sum fits
if (tot <= sum) {
// Update the answer
ans = Math.max(ans, r - l);
if (r == n)
break;
// Update the total sum
tot += arr[r++];
}
else {
// Increment the left pointer
tot -= arr[l++];
}
}
return (n - ans);
}
// Driver code
var arr = [1, 11, 5, 5 ];
var n = arr.length;
var k = 11;
document.write( minCount(arr, n, k));
// This code is contributed by noob2000.
</script>
2
Publicación traducida automáticamente
Artículo escrito por DivyanshuShekhar1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA