Dado un entero K y una array arr[] que consta de N enteros, la tarea es encontrar la longitud del subarreglo de longitud más pequeña posible que se eliminará de modo que la cantidad de elementos de la array menores y mayores que K en la array restante sea igual.
Ejemplos:
Entrada: arr[] = {5, 7, 2, 8, 7, 4, 5, 9}, K = 5 Salida:
2 Explicación
:
El subarreglo más pequeño que se requiere eliminar es {8, 7}, para hacer el resultante más grande array {5, 7, 2, 4, 5, 9} satisface la condición dada.Entrada: arr[] = {12, 16, 12, 13, 10}, K = 13
Salida: 3
Explicación:
el subarreglo más pequeño que se requiere eliminar es {12, 13, 10} para hacer el arreglo resultante más grande {12, 16 } satisface la condición dada.
Enfoque ingenuo: el enfoque más simple para resolver el problema es generar todos los subarreglos posibles y recorrer el resto del arreglo para llevar la cuenta de los elementos del arreglo que son estrictamente mayores y menores que el entero K. Luego, seleccione el subarreglo más pequeño cuya eliminación dé como resultado un arreglo que tenga el mismo número de elementos más pequeños y más grandes.
Tiempo Complejidad: O(N 2 )
Espacio Auxiliar: O(N 2 )
Enfoque eficiente: la idea es usar Hashing con alguna modificación en la array para resolverlo en tiempo O (N) . La array dada puede tener 3 tipos de elementos:
- elemento = K : cambiar elemento a 0 (porque necesitamos elementos que sean estrictamente mayores que K o menores que K )
- elemento > K : cambiar elemento a 1
- elemento < K : cambiar elemento a -1
Ahora, calcule la suma de todos los elementos de la array y guárdela en una variable, digamos total_sum . Ahora, total_sum puede tener tres posibles rangos de valores:
- Si total_sum = 0 : todos los 1 se cancelan con -1. Entonces, el mismo número de elementos mayores y menores que K ya están presentes. No se requiere ninguna operación de eliminación. Por lo tanto, imprima 0 como la respuesta requerida.
- Si suma_total > 0 : algunos 1 se dejan sin cancelar por -1. es decir , la array tiene más elementos mayores que K y menos elementos menores que K. Por lo tanto, encuentre el subarreglo más pequeño de sum = total_sum , ya que es el subarreglo más pequeño que se eliminará.
- Si suma_total < 0: algunos -1 se dejan sin cancelar por 1. es decir, la array tiene más cantidad de elementos más pequeños que k y menos cantidad de elementos más grandes que K. Por lo tanto, encuentre el subarreglo más pequeño de sum = total_sum , ya que es el subarreglo más pequeño que se eliminará.
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 ot find the length
// of the smallest subarray
int smallSubarray(int arr[], int n,
int total_sum)
{
// Stores (prefix Sum, index)
// as (key, value) mappings
unordered_map<int, int> m;
int length = INT_MAX;
int prefixSum = 0;
// Iterate till N
for (int i = 0; i < n; i++) {
// Update the prefixSum
prefixSum += arr[i];
// Update the length
if (prefixSum == total_sum) {
length = min(length, i + 1);
}
// Put the latest index to
// find the minimum length
m[prefixSum] = i;
if (m.count(prefixSum - total_sum)) {
// Update the length
length
= min(length,
i - m[prefixSum - total_sum]);
}
}
// Return the answer
return length;
}
// Function to find the length of
// the largest subarray
int smallestSubarrayremoved(int arr[], int n,
int k)
{
// Stores the sum of all array
// elements after modification
int total_sum = 0;
for (int i = 0; i < n; i++) {
// Change greater than k to 1
if (arr[i] > k) {
arr[i] = 1;
}
// Change smaller than k to -1
else if (arr[i] < k) {
arr[i] = -1;
}
// Change equal to k to 0
else {
arr[i] = 0;
}
// Update total_sum
total_sum += arr[i];
}
// No deletion required, return 0
if (total_sum == 0) {
return 0;
}
else {
// Delete smallest subarray
// that has sum = total_sum
return smallSubarray(arr, n,
total_sum);
}
}
// Driver Code
int main()
{
int arr[] = { 12, 16, 12, 13, 10 };
int K = 13;
int n = sizeof(arr) / sizeof(int);
cout << smallestSubarrayremoved(
arr, n, K);
return 0;
}
Java
// Java program to implement
// the above approach
import java.util.*;
class GFG{
// Function ot find the length
// of the smallest subarray
static int smallSubarray(int arr[], int n,
int total_sum)
{
// Stores (prefix Sum, index)
// as (key, value) mappings
Map<Integer,
Integer> m = new HashMap<Integer,
Integer>();
int length = Integer.MAX_VALUE;
int prefixSum = 0;
// Iterate till N
for(int i = 0; i < n; i++)
{
// Update the prefixSum
prefixSum += arr[i];
// Update the length
if (prefixSum == total_sum)
{
length = Math.min(length, i + 1);
}
// Put the latest index to
// find the minimum length
m.put(prefixSum, i);
if (m.containsKey(prefixSum - total_sum))
{
// Update the length
length = Math.min(length,
i - m.get(prefixSum -
total_sum));
}
}
// Return the answer
return length;
}
// Function to find the length of
// the largest subarray
static int smallestSubarrayremoved(int arr[], int n,
int k)
{
// Stores the sum of all array
// elements after modification
int total_sum = 0;
for(int i = 0; i < n; i++)
{
// Change greater than k to 1
if (arr[i] > k)
{
arr[i] = 1;
}
// Change smaller than k to -1
else if (arr[i] < k)
{
arr[i] = -1;
}
// Change equal to k to 0
else
{
arr[i] = 0;
}
// Update total_sum
total_sum += arr[i];
}
// No deletion required, return 0
if (total_sum == 0)
{
return 0;
}
else
{
// Delete smallest subarray
// that has sum = total_sum
return smallSubarray(arr, n, total_sum);
}
}
// Driver Code
public static void main(String[] args)
{
int arr[] = { 12, 16, 12, 13, 10 };
int K = 13;
int n = arr.length;
System.out.println(
smallestSubarrayremoved(arr, n, K));
}
}
// This code is contributed by chitranayal
Python3
# Python3 program to implement
# the above approach
import sys
# Function ot find the length
# of the smallest subarray
def smallSubarray(arr, n, total_sum):
# Stores (prefix Sum, index)
# as (key, value) mappings
m = {}
length = sys.maxsize
prefixSum = 0
# Iterate till N
for i in range(n):
# Update the prefixSum
prefixSum += arr[i]
# Update the length
if(prefixSum == total_sum):
length = min(length, i + 1)
# Put the latest index to
# find the minimum length
m[prefixSum] = i
if((prefixSum - total_sum) in m.keys()):
# Update the length
length = min(length,
i - m[prefixSum - total_sum])
# Return the answer
return length
# Function to find the length of
# the largest subarray
def smallestSubarrayremoved(arr, n, k):
# Stores the sum of all array
# elements after modification
total_sum = 0
for i in range(n):
# Change greater than k to 1
if(arr[i] > k):
arr[i] = 1
# Change smaller than k to -1
elif(arr[i] < k):
arr[i] = -1
# Change equal to k to 0
else:
arr[i] = 0
# Update total_sum
total_sum += arr[i]
# No deletion required, return 0
if(total_sum == 0):
return 0
else:
# Delete smallest subarray
# that has sum = total_sum
return smallSubarray(arr, n,
total_sum)
# Driver Code
arr = [ 12, 16, 12, 13, 10 ]
K = 13
n = len(arr)
# Function call
print(smallestSubarrayremoved(arr, n, K))
# This code is contributed by Shivam Singh
C#
// C# program to implement
// the above approach
using System;
using System.Collections.Generic;
class GFG{
// Function ot find the length
// of the smallest subarray
static int smallSubarray(int []arr, int n,
int total_sum)
{
// Stores (prefix Sum, index)
// as (key, value) mappings
Dictionary<int,
int> m = new Dictionary<int,
int>();
int length = int.MaxValue;
int prefixSum = 0;
// Iterate till N
for(int i = 0; i < n; i++)
{
// Update the prefixSum
prefixSum += arr[i];
// Update the length
if (prefixSum == total_sum)
{
length = Math.Min(length, i + 1);
}
// Put the latest index to
// find the minimum length
if (m.ContainsKey(prefixSum))
m[prefixSum] = i;
else
m.Add(prefixSum, i);
if (m.ContainsKey(prefixSum - total_sum))
{
// Update the length
length = Math.Min(length,
i - m[prefixSum -
total_sum]);
}
}
// Return the answer
return length;
}
// Function to find the length of
// the largest subarray
static int smallestSubarrayremoved(int []arr,
int n, int k)
{
// Stores the sum of all array
// elements after modification
int total_sum = 0;
for(int i = 0; i < n; i++)
{
// Change greater than k to 1
if (arr[i] > k)
{
arr[i] = 1;
}
// Change smaller than k to -1
else if (arr[i] < k)
{
arr[i] = -1;
}
// Change equal to k to 0
else
{
arr[i] = 0;
}
// Update total_sum
total_sum += arr[i];
}
// No deletion required, return 0
if (total_sum == 0)
{
return 0;
}
else
{
// Delete smallest subarray
// that has sum = total_sum
return smallSubarray(arr, n, total_sum);
}
}
// Driver Code
public static void Main(String[] args)
{
int []arr = { 12, 16, 12, 13, 10 };
int K = 13;
int n = arr.Length;
Console.WriteLine(
smallestSubarrayremoved(arr, n, K));
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// Javascript program to implement
// the above approach
// Function ot find the length
// of the smallest subarray
function smallSubarray(arr,n,total_sum)
{
// Stores (prefix Sum, index)
// as (key, value) mappings
let m = new Map();
let length = Number.MAX_VALUE;
let prefixSum = 0;
// Iterate till N
for(let i = 0; i < n; i++)
{
// Update the prefixSum
prefixSum += arr[i];
// Update the length
if (prefixSum == total_sum)
{
length = Math.min(length, i + 1);
}
// Put the latest index to
// find the minimum length
m.set(prefixSum, i);
if (m.has(prefixSum - total_sum))
{
// Update the length
length = Math.min(length,
i - m.get(prefixSum -
total_sum));
}
}
// Return the answer
return length;
}
// Function to find the length of
// the largest subarray
function smallestSubarrayremoved(arr,n,k)
{
// Stores the sum of all array
// elements after modification
let total_sum = 0;
for(let i = 0; i < n; i++)
{
// Change greater than k to 1
if (arr[i] > k)
{
arr[i] = 1;
}
// Change smaller than k to -1
else if (arr[i] < k)
{
arr[i] = -1;
}
// Change equal to k to 0
else
{
arr[i] = 0;
}
// Update total_sum
total_sum += arr[i];
}
// No deletion required, return 0
if (total_sum == 0)
{
return 0;
}
else
{
// Delete smallest subarray
// that has sum = total_sum
return smallSubarray(arr, n, total_sum);
}
}
// Driver Code
let arr=[12, 16, 12, 13, 10];
let K = 13;
let n = arr.length;
document.write(smallestSubarrayremoved(arr, n, K));
// This code is contributed by avanitrachhadiya2155
</script>
Producción:
3
Complejidad temporal: O(N)
Espacio auxiliar: O(N)