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>
3
Complejidad temporal: O(N)
Espacio auxiliar: O(N)