Dado un entero K y una array A[] de tamaño N , la tarea es crear una nueva array con suma K con un número mínimo de operaciones, donde en cada operación, un elemento puede eliminarse desde el principio o el final de A[ ] y se adjunta a la nueva array. Si no es posible generar una nueva array con suma K , imprima -1 . Si hay varias respuestas, imprima cualquiera de ellas.
Ejemplos
Entrada: K = 6, A[] = {1, 2, 3, 1, 3}, N = 5
Salida: 1 3 2
Explicación: Operación 1: Eliminar A[0] modifica A[] a {2, 3, 1, 3}. Suma = 1.
Operación 2: Eliminar A[3] modifica A[] a {2, 1, 3}. Suma = 4.
Operación 3: Eliminar A[0] modifica A[] a {1, 3}. Suma = 6.Entrada: K = 5, A[] = {1, 2, 7}, N = 3
Salida: -1
Enfoque ingenuo: siga los pasos a continuación para resolver el problema:
- La tarea es encontrar dos subarreglos de longitud mínima, uno desde el principio y otro desde el final del arreglo (posiblemente vacío), tal que su suma sea igual a K .
- Atraviese el arreglo desde la izquierda y calcule el subarreglo que debe eliminarse desde la derecha de modo que la suma total sea K .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to find the minimum number of // elements required to be removed from // the ends of an array to obtain a sum K int minSizeArr(int A[], int N, int K) { // Number of elements removed from the // left and right ends of the array int leftTaken = N, rightTaken = N; // Sum of left and right subarrays int leftSum = 0, rightSum = 0; // No element is taken from left initially for (int left = -1; left < N; left++) { if (left != -1) leftSum += A[left]; rightSum = 0; // Start taking elements from right side for (int right = N - 1; right > left; right--) { rightSum += A[right]; if (leftSum + rightSum == K) { // (left + 1): Count of elements // removed from the left // (N-right): Count of elements // removed from the right if (leftTaken + rightTaken > (left + 1) + (N - right)) { leftTaken = left + 1; rightTaken = N - right; } break; } // If sum is greater than K if (leftSum + rightSum > K) break; } } if (leftTaken + rightTaken <= N) { for (int i = 0; i < leftTaken; i++) cout << A[i] << " "; for (int i = 0; i < rightTaken; i++) cout << A[N - i - 1] << " "; } // If it is not possible to obtain sum K else cout << -1; } // Driver Code int main() { int N = 7; // Given Array int A[] = { 3, 2, 1, 1, 1, 1, 3 }; // Given target sum int K = 10; minSizeArr(A, N, K); return 0; }
Java
// Java program for the above approach import java.util.*; class GFG{ // Function to find the minimum number of // elements required to be removed from // the ends of an array to obtain a sum K static void minSizeArr(int A[], int N, int K) { // Number of elements removed from the // left and right ends of the array int leftTaken = N, rightTaken = N; // Sum of left and right subarrays int leftSum = 0, rightSum = 0; // No element is taken from left initially for (int left = -1; left < N; left++) { if (left != -1) leftSum += A[left]; rightSum = 0; // Start taking elements from right side for (int right = N - 1; right > left; right--) { rightSum += A[right]; if (leftSum + rightSum == K) { // (left + 1): Count of elements // removed from the left // (N-right): Count of elements // removed from the right if (leftTaken + rightTaken > (left + 1) + (N - right)) { leftTaken = left + 1; rightTaken = N - right; } break; } // If sum is greater than K if (leftSum + rightSum > K) break; } } if (leftTaken + rightTaken <= N) { for (int i = 0; i < leftTaken; i++) System.out.print( A[i] + " "); for (int i = 0; i < rightTaken; i++) System.out.print(A[N - i - 1] + " "); } // If it is not possible to obtain sum K else System.out.print(-1); } // Driver code public static void main(String[] args) { int N = 7; // Given Array int A[] = { 3, 2, 1, 1, 1, 1, 3 }; // Given target sum int K = 10; minSizeArr(A, N, K); } } // This code is contributed by splevel62.
Python3
# Python3 program for the above approach # Function to find the minimum number of # elements required to be removed from # the ends of an array to obtain a sum K def minSizeArr(A, N, K): # Number of elements removed from the # left and right ends of the array leftTaken = N rightTaken = N # Sum of left and right subarrays leftSum = 0 rightSum = 0 # No element is taken from left initially for left in range(-1, N): if (left != -1): leftSum += A[left] rightSum = 0 # Start taking elements from right side for right in range(N - 1, left, -1): rightSum += A[right] if (leftSum + rightSum == K): # (left + 1): Count of elements # removed from the left # (N-right): Count of elements # removed from the right if (leftTaken + rightTaken > (left + 1) + (N - right)): leftTaken = left + 1 rightTaken = N - right break # If sum is greater than K if (leftSum + rightSum > K): break if (leftTaken + rightTaken <= N): for i in range(leftTaken): print(A[i], end = " ") for i in range(rightTaken): print(A[N - i - 1], end = " ") # If it is not possible to obtain sum K else: print(-1) # Driver Code if __name__ == "__main__": N = 7 # Given Array A = [ 3, 2, 1, 1, 1, 1, 3 ] # Given target sum K = 10 minSizeArr(A, N, K) # This code is contributed by ukasp
C#
// C# program for the above approach using System; class GFG { // Function to find the smallest // array that can be removed from // the ends of an array to obtain sum K static void minSizeArr(int[] A, int N, int K) { // Number of elements removed from the // left and right ends of the array int leftTaken = N, rightTaken = N; // Sum of left and right subarrays int leftSum = 0, rightSum = 0; // No element is taken from left initially for (int left = -1; left < N; left++) { if (left != -1) leftSum += A[left]; rightSum = 0; // Start taking elements from right side for (int right = N - 1; right > left; right--) { rightSum += A[right]; if (leftSum + rightSum == K) { // (left + 1): Count of elements // removed from the left // (N-right): Count of elements // removed from the right if (leftTaken + rightTaken > (left + 1) + (N - right)) { leftTaken = left + 1; rightTaken = N - right; } break; } // If sum is greater than K if (leftSum + rightSum > K) break; } } if (leftTaken + rightTaken <= N) { for (int i = 0; i < leftTaken; i++) Console.Write( A[i] + " "); for (int i = 0; i < rightTaken; i++) Console.Write(A[N - i - 1] + " "); } // If it is not possible to obtain sum K else Console.Write(-1); } // Driver Code public static void Main() { int N = 7; // Given Array int[] A = { 3, 2, 1, 1, 1, 1, 3 }; // Given target sum int K = 10; minSizeArr(A, N, K); } } // This code is contributed by code_hunt.
Javascript
<script> // JavaScript program for the above approach // Function to find the minimum number of // elements required to be removed from // the ends of an array to obtain a sum K function minSizeArr(A, N, K) { // Number of elements removed from the // left and right ends of the array let leftTaken = N, rightTaken = N; // Sum of left and right subarrays let leftSum = 0, rightSum = 0; // No element is taken from left initially for (let left = -1; left < N; left++) { if (left != -1) leftSum += A[left]; rightSum = 0; // Start taking elements from right side for (let right = N - 1; right > left; right--) { rightSum += A[right]; if (leftSum + rightSum == K) { // (left + 1): Count of elements // removed from the left // (N-right): Count of elements // removed from the right if (leftTaken + rightTaken > (left + 1) + (N - right)) { leftTaken = left + 1; rightTaken = N - right; } break; } // If sum is greater than K if (leftSum + rightSum > K) break; } } if (leftTaken + rightTaken <= N) { for (let i = 0; i < leftTaken; i++) document.write( A[i] + " "); for (let i = 0; i < rightTaken; i++) document.write(A[N - i - 1] + " "); } // If it is not possible to obtain sum K else document.write(-1); } // Driver code let N = 7; // Given Array let A = [ 3, 2, 1, 1, 1, 1, 3 ]; // Given target sum let K = 10; minSizeArr(A, N, K); // This code is contributed by souraavghosh0416. </script>
3 2 3 1 1
Complejidad de Tiempo: O(N 2 )
Espacio Auxiliar: O(1)
Enfoque eficiente: siga los pasos a continuación para optimizar el enfoque anterior:
- Calcule la suma de los elementos de la array A[] y guárdela en una variable, digamos Total .
- El problema puede verse como encontrar el subarreglo de tamaño máximo con suma (Total – K).
- Los elementos restantes se sumarán a K .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to find the smallest // array that can be removed from // the ends of an array to obtain sum K void minSizeArr(int A[], int N, int K) { int sum = 0; // Sum of complete array for (int i = 0; i < N; i++) sum += A[i]; // If given number is greater // than sum of the array if (K > sum) { cout << -1; return; } // If number is equal to // the sum of array if (K == sum) { for (int i = 0; i < N; i++) { cout << A[i] << " "; } return; } // tar is sum of middle subarray int tar = sum - K; // Find the longest subarray // with sum equal to tar unordered_map<int, int> um; um[0] = -1; int left, right; int cur = 0, maxi = -1; for (int i = 0; i < N; i++) { cur += A[i]; if (um.find(cur - tar) != um.end() && i - um[cur - tar] > maxi) { maxi = i - um[cur - tar]; right = i; left = um[cur - tar]; } if (um.find(cur) == um.end()) um[cur] = i; } // If there is no subarray with // sum equal to tar if (maxi == -1) cout << -1; else { for (int i = 0; i <= left; i++) cout << A[i] << " "; for (int i = 0; i < right; i++) cout << A[N - i - 1] << " "; } } // Driver Code int main() { int N = 7; // Given Array int A[] = { 3, 2, 1, 1, 1, 1, 3 }; // Given target sum int K = 10; minSizeArr(A, N, K); return 0; }
Java
// Java program for the above approach import java.io.*; import java.util.*; class GFG { // Function to find the smallest // array that can be removed from // the ends of an array to obtain sum K static void minSizeArr(int A[], int N, int K) { int sum = 0; // Sum of complete array for (int i = 0; i < N; i++) sum += A[i]; // If given number is greater // than sum of the array if (K > sum) { System.out.print(-1); return; } // If number is equal to // the sum of array if (K == sum) { for (int i = 0; i < N; i++) { System.out.print(A[i] + " "); } return; } // tar is sum of middle subarray int tar = sum - K; // Find the longest subarray // with sum equal to tar HashMap<Integer, Integer> um = new HashMap<Integer, Integer>(); um.put(0, -1); int left = 0, right = 0; int cur = 0, maxi = -1; for (int i = 0; i < N; i++) { cur += A[i]; if (um.containsKey(cur - tar) && i - um.get(cur - tar) > maxi) { maxi = i - um.get(cur - tar); right = i; left = um.get(cur - tar); } if (!um.containsKey(cur)) um.put(cur, i); } // If there is no subarray with // sum equal to tar if (maxi == -1) System.out.println(-1); else { for (int i = 0; i <= left; i++) System.out.print(A[i] + " "); for (int i = 0; i < right; i++) System.out.print(A[N - i - 1] + " "); } } // Driver Code public static void main (String[] args) { int N = 7; // Given Array int A[] = { 3, 2, 1, 1, 1, 1, 3 }; // Given target sum int K = 10; minSizeArr(A, N, K); } } // This code is contributed by Dharanendra L V.
Python3
# python 3 program for the above approach # Function to find the smallest # array that can be removed from # the ends of an array to obtain sum K def minSizeArr(A, N, K): sum = 0 # Sum of complete array for i in range(N): sum += A[i] # If given number is greater # than sum of the array if (K > sum): print(-1); return # If number is equal to # the sum of array if (K == sum): for i in range(N): print(A[i],end = " ") return # tar is sum of middle subarray tar = sum - K # Find the longest subarray # with sum equal to tar um = {} um[0] = -1 left = 0 right = 0 cur = 0 maxi = -1 for i in range(N): cur += A[i] if((cur - tar) in um and (i - um[cur - tar]) > maxi): maxi = i - um[cur - tar] right = i left = um[cur - tar] if(cur not in um): um[cur] = i # If there is no subarray with # sum equal to tar if (maxi == -1): print(-1) else: for i in range(left+1): print(A[i], end = " ") for i in range(right): print(A[N - i - 1], end = " ") # Driver Code if __name__ == '__main__': N = 7 # Given Array A = [3, 2, 1, 1, 1, 1, 3] # Given target sum K = 10 minSizeArr(A, N, K) # This code is contributed by SURENDRA_GANGWAR.
C#
// C# program for // the above approach using System; using System.Collections.Generic; class GFG{ // Function to find the smallest // array that can be removed from // the ends of an array to obtain sum K static void minSizeArr(int[] A, int N, int K) { int sum = 0; // Sum of complete array for(int i = 0; i < N; i++) sum += A[i]; // If given number is greater // than sum of the array if (K > sum) { Console.WriteLine(-1); return; } // If number is equal to // the sum of array if (K == sum) { for(int i = 0; i < N; i++) { Console.Write(A[i] + " "); } return; } // tar is sum of middle subarray int tar = sum - K; // Find the longest subarray // with sum equal to tar Dictionary<int, int> um = new Dictionary<int, int>(); um[0] = -1; int left = 0, right = 0; int cur = 0, maxi = -1; for(int i = 0; i < N; i++) { cur += A[i]; if (um.ContainsKey(cur - tar) && i - um[cur - tar] > maxi) { maxi = i - um[cur - tar]; right = i; left = um[cur - tar]; } if (!um.ContainsKey(cur)) um[cur] = i; } // If there is no subarray with // sum equal to tar if (maxi == -1) Console.Write(-1); else { for(int i = 0; i <= left; i++) Console.Write(A[i] + " "); for(int i = 0; i < right; i++) Console.Write(A[N - i - 1] + " "); } } // Driver code static public void Main() { int N = 7; // Given Array int[] A = { 3, 2, 1, 1, 1, 1, 3 }; // Given target sum int K = 10; minSizeArr(A, N, K); } } // This code is contributed by offbeat
Javascript
<script> // JavaScript program for the above approach // Function to find the smallest // array that can be removed from // the ends of an array to obtain sum K function minSizeArr(A, N, K) { var sum = 0; var i; // Sum of complete array for (i = 0; i < N; i++) sum += A[i]; // If given number is greater // than sum of the array if (K > sum) { cout << -1; return; } // If number is equal to // the sum of array if (K == sum) { for (i = 0; i < N; i++) { document.write(A[i]+' '); } return; } // tar is sum of middle subarray var tar = sum - K; // Find the longest subarray // with sum equal to tar var um = new Map(); um[0] = -1; var left, right; var cur = 0, maxi = -1; for (i = 0; i < N; i++) { cur += A[i]; if (um.has(cur - tar) && i - um.get(cur - tar) > maxi) { maxi = i - um.get(cur - tar); right = i; left = um.get(cur - tar); } if (!um.has(cur)) um.set(cur,i); } // If there is no subarray with // sum equal to tar if (maxi == -1) cout << -1; else { for (i = 0; i <= left; i++) document.write(A[i]+' '); for (i = 0; i < right; i++) document.write(A[N - i - 1]+ ' '); } } // Driver Code var N = 7; // Given Array var A = [3, 2, 1, 1, 1, 1, 3]; // Given target sum var K = 10; minSizeArr(A, N, K); </script>
3 2 3 1 1
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Tema relacionado: Subarrays, subsecuencias y subconjuntos en array
Publicación traducida automáticamente
Artículo escrito por sachinjain74754 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA