Dada una array arr[] de enteros y un entero k , la tarea es encontrar el número mínimo de enteros que deben eliminarse de la array de modo que la suma de los elementos restantes sea igual a k . Si no podemos obtener la suma requerida, la impresión -1 .
Ejemplos:
Entrada: arr[] = {1, 2, 3}, k = 3
Salida: 1
Quite 1 y 2 para reducir el arreglo a {3}
o quite 3 para obtener el arreglo {1, 2}. Ambos tienen la misma suma, es decir, 3
, pero eliminar 3 requiere solo una eliminación.
Entrada: arr[] = {1, 3, 2, 5, 6}, k = 5
Salida: 3
Enfoque: La idea es usar una ventana deslizante y las variables j inicializarlo a 0, min_num para almacenar la respuesta y suma para almacenar la suma actual. Continúe agregando los elementos de la array a la variable sum , hasta que sea mayor o igual a k, si es igual a k, luego actualice min_num como mínimo de min_num y (n -(i+1) +j) donde n es el número de enteros en la array e i es el índice actual, de lo contrario, si es mayor que k, comience a disminuir la suma eliminando los valores de la array de la suma hasta que la suma sea menor o igual a k y también incremente el valor de j , si la suma es igual a k, luego actualice una vez másmin_num . Repita todo este proceso hasta el final de la array.
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 minimum number of
// integers that need to be removed from the
// array to form a sub-array with sum k
int FindMinNumber(int arr[], int n, int k)
{
int i = 0;
int j = 0;
// Stores the minimum number of
// integers that need to be removed
// from the array
int min_num = INT_MAX;
bool found = false;
int sum = 0;
while (i < n) {
sum = sum + arr[i];
// If current sum is equal to
// k, update min_num
if (sum == k) {
min_num = min(min_num, ((n - (i + 1)) + j));
found = true;
}
// If current sum is greater than k
else if (sum > k) {
// Decrement the sum until it
// becomes less than or equal to k
while (sum > k) {
sum = sum - arr[j];
j++;
}
if (sum == k) {
min_num = min(min_num, ((n - (i + 1)) + j));
found = true;
}
}
i++;
}
if (found)
return min_num;
return -1;
}
// Driver code
int main()
{
int arr[] = { 1, 3, 2, 5, 6 };
int n = sizeof(arr) / sizeof(int);
int k = 5;
cout << FindMinNumber(arr, n, k);
return 0;
}
Java
// Java implementation of the approach
class GFG
{
// Function to return the minimum number of
// integers that need to be removed from the
// array to form a sub-array with sum k
static int FindMinNumber(int arr[], int n, int k)
{
int i = 0;
int j = 0;
// Stores the minimum number of
// integers that need to be removed
// from the array
int min_num = Integer.MAX_VALUE;
boolean found = false;
int sum = 0;
while (i < n)
{
sum = sum + arr[i];
// If current sum is equal to
// k, update min_num
if (sum == k)
{
min_num = Math.min(min_num,
((n - (i + 1)) + j));
found = true;
}
// If current sum is greater than k
else if (sum > k)
{
// Decrement the sum until it
// becomes less than or equal to k
while (sum > k)
{
sum = sum - arr[j];
j++;
}
if (sum == k)
{
min_num = Math.min(min_num,
((n - (i + 1)) + j));
found = true;
}
}
i++;
}
if (found)
return min_num;
return -1;
}
// Driver code
public static void main(String[] args)
{
int arr[] = { 1, 3, 2, 5, 6 };
int n = arr.length;
int k = 5;
System.out.println(FindMinNumber(arr, n, k));
}
}
// This code is contributed by Code_Mech
Python3
# Python3 implementation of the approach # Function to return the minimum number of # integers that need to be removed from the # array to form a sub-array with Sum k def FindMinNumber(arr, n, k): i = 0 j = 0 # Stores the minimum number of # integers that need to be removed # from the array min_num = 10**9 found = False Sum = 0 while (i < n): Sum = Sum + arr[i] # If current Sum is equal to # k, update min_num if (Sum == k): min_num = min(min_num, ((n - (i + 1)) + j)) found = True # If current Sum is greater than k elif (Sum > k): # Decrement the Sum until it # becomes less than or equal to k while (Sum > k): Sum = Sum - arr[j] j += 1 if (Sum == k): min_num = min(min_num, ((n - (i + 1)) + j)) found = True i += 1 if (found): return min_num return -1 # Driver code arr = [1, 3, 2, 5, 6] n = len(arr) k = 5 print(FindMinNumber(arr, n, k)) # This code is contributed by mohit kumar
C#
// C# implementation of the approach
using System;
class GFG
{
// Function to return the minimum number of
// integers that need to be removed from the
// array to form a sub-array with sum k
static int FindMinNumber(int[] arr, int n, int k)
{
int i = 0;
int j = 0;
// Stores the minimum number of
// integers that need to be removed
// from the array
int min_num = int.MaxValue;
bool found = false;
int sum = 0;
while (i < n)
{
sum = sum + arr[i];
// If current sum is equal to
// k, update min_num
if (sum == k)
{
min_num = Math.Min(min_num,
((n - (i + 1)) + j));
found = true;
}
// If current sum is greater than k
else if (sum > k)
{
// Decrement the sum until it
// becomes less than or equal to k
while (sum > k)
{
sum = sum - arr[j];
j++;
}
if (sum == k)
{
min_num = Math.Min(min_num,
((n - (i + 1)) + j));
found = true;
}
}
i++;
}
if (found)
return min_num;
return -1;
}
// Driver code
public static void Main()
{
int[] arr = { 1, 3, 2, 5, 6 };
int n = arr.Length;
int k = 5;
Console.WriteLine(FindMinNumber(arr, n, k));
}
}
// This code is contributed by Code_Mech
PHP
<?php
// PHP implementation of the approach
// Function to return the minimum number of
// integers that need to be removed from the
// array to form a sub-array with sum k
function FindMinNumber($arr,$n,$k)
{
$i = 0;
$j = 0;
// Stores the minimum number of
// integers that need to be removed
// from the array
$min_num = PHP_INT_MAX;
$found = false;
$sum = 0;
while ($i < $n)
{
$sum = $sum + $arr[$i];
// If current sum is equal to
// k, update min_num
if ($sum == $k)
{
$min_num = min($min_num,
(($n - ($i + 1)) + $j));
$found = true;
}
// If current sum is greater than k
else if ($sum > $k)
{
// Decrement the sum until it
// becomes less than or equal to k
while ($sum > $k)
{
$sum = $sum - $arr[$j];
$j++;
}
if ($sum == $k)
{
$min_num =min($min_num,
(($n - ($i + 1)) + $j));
$found = true;
}
}
$i++;
}
if ($found)
return $min_num;
return -1;
}
// Driver code
$arr = array( 1, 3, 2, 5, 6 );
$n = sizeof($arr);
$k = 5;
echo(FindMinNumber($arr, $n, $k));
// This code is contributed by Code_Mech
Javascript
<script>
// Javascript implementation of the approach
// Function to return the minimum number of
// integers that need to be removed from the
// array to form a sub-array with sum k
function FindMinNumber(arr,n,k)
{
let i = 0;
let j = 0;
// Stores the minimum number of
// integers that need to be removed
// from the array
let min_num = Number.MAX_VALUE;
let found = false;
let sum = 0;
while (i < n)
{
sum = sum + arr[i];
// If current sum is equal to
// k, update min_num
if (sum == k)
{
min_num = Math.min(min_num,
((n - (i + 1)) + j));
found = true;
}
// If current sum is greater than k
else if (sum > k)
{
// Decrement the sum until it
// becomes less than or equal to k
while (sum > k)
{
sum = sum - arr[j];
j++;
}
if (sum == k)
{
min_num = Math.min(min_num,
((n - (i + 1)) + j));
found = true;
}
}
i++;
}
if (found)
return min_num;
return -1;
}
// Driver code
let arr = [1, 3, 2, 5, 6 ];
let n = arr.length;
let k = 5;
document.write(FindMinNumber(arr, n, k));
// This code is contributed by patel2127
</script>
Producción:
3
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por Sakshi_Srivastava y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA