Dado un arreglo A[] que consta de N enteros positivos y un entero K , la tarea es encontrar la longitud del subarreglo más pequeño con una suma mayor o igual a K . Si no existe tal subarreglo, imprima -1 .
Ejemplos:
Entrada: arr[] = {3, 1, 7, 1, 2}, K = 11
Salida: 3
Explicación:
El subarreglo más pequeño con suma ≥ K(= 11) es {3, 1, 7}.Entrada: arr[] = {2, 3, 5, 4, 1}, K = 11
Salida: 3
Explicación:
El subarreglo mínimo posible es {3, 5, 4}.
Enfoque de búsqueda ingenua y binaria: consulte el subarreglo más pequeño de un conjunto dado con una suma mayor o igual a K para el enfoque más simple y los enfoques basados en la búsqueda binaria para resolver el problema.
Enfoque recursivo: el enfoque más simple para resolver el problema es usar Recursion . Siga los pasos a continuación para resolver el problema:
- Si K ≤ 0: Imprima -1 ya que no se puede obtener dicho subarreglo.
- Si la suma de la array es igual a K , imprima la longitud de la array como la respuesta requerida.
- Si el primer elemento de la array es mayor que K , imprima 1 como la respuesta requerida.
- De lo contrario, proceda a encontrar el subarreglo más pequeño considerando el elemento actual en el subarreglo y no incluyéndolo.
- Repita los pasos anteriores para cada elemento atravesado.
A continuación se muestra la implementación del enfoque anterior:
C++14
// C++14 program for the above approach #include <bits/stdc++.h> using namespace std; // Function to find the smallest subarray // sum greater than or equal to target int smallSumSubset(vector<int> data, int target, int maxVal) { int sum = 0; for(int i : data) sum += i; // Base Case if (target <= 0) return 0; // If sum of the array // is less than target else if (sum < target) return maxVal; // If target is equal to // the sum of the array else if (sum == target) return data.size(); // Required condition else if (data[0] >= target) return 1; else if (data[0] < target) { vector<int> temp; for(int i = 1; i < data.size(); i++) temp.push_back(data[i]); return min(smallSumSubset(temp, target, maxVal), 1 + smallSumSubset(temp, target - data[0], maxVal)); } } // Driver Code int main() { vector<int> data = { 3, 1, 7, 1, 2 }; int target = 11; int val = smallSumSubset(data, target, data.size() + 1); if (val > data.size()) cout << -1; else cout << val; } // This code is contributed by mohit kumar 29
Java
// Java program for the above approach import java.util.*; import java.lang.*; class GFG{ // Function to find the smallest subarray // sum greater than or equal to target static int smallSumSubset(List<Integer> data, int target, int maxVal) { int sum = 0; for(Integer i : data) sum += i; // Base Case if (target <= 0) return 0; // If sum of the array // is less than target else if (sum < target) return maxVal; // If target is equal to // the sum of the array else if (sum == target) return data.size(); // Required condition else if (data.get(0) >= target) return 1; else if (data.get(0) < target) { List<Integer> temp = new ArrayList<>(); for(int i = 1; i < data.size(); i++) temp.add(data.get(i)); return Math.min(smallSumSubset(temp, target, maxVal), 1 + smallSumSubset(temp, target - data.get(0), maxVal)); } return -1; } // Driver Code public static void main (String[] args) { List<Integer> data = Arrays.asList(3, 1, 7, 1, 2); int target = 11; int val = smallSumSubset(data, target, data.size() + 1); if (val > data.size()) System.out.println(-1); else System.out.println(val); } } // This code is contributed by offbeat
Python3
# Python3 program for the above approach # Function to find the smallest subarray # sum greater than or equal to target def smallSumSubset(data, target, maxVal): # base condition # Base Case if target <= 0: return 0 # If sum of the array # is less than target elif sum(data) < target: return maxVal # If target is equal to # the sum of the array elif sum(data) == target: return len(data) # Required condition elif data[0] >= target: return 1 elif data[0] < target: return min(smallSumSubset(data[1:], \ target, maxVal), 1 + smallSumSubset(data[1:], \ target-data[0], maxVal)) # Driver Code data = [3, 1, 7, 1, 2] target = 11 val = smallSumSubset(data, target, len(data)+1) if val > len(data): print(-1) else: print(val)
C#
// C# program for the above approach using System; using System.Collections.Generic; class GFG{ // Function to find the smallest subarray // sum greater than or equal to target static int smallSumSubset(List<int> data, int target, int maxVal) { int sum = 0; foreach(int i in data) sum += i; // Base Case if (target <= 0) return 0; // If sum of the array // is less than target else if (sum < target) return maxVal; // If target is equal to // the sum of the array else if (sum == target) return data.Count; // Required condition else if (data[0] >= target) return 1; else if (data[0] < target) { List<int> temp = new List<int>(); for(int i = 1; i < data.Count; i++) temp.Add(data[i]); return Math.Min(smallSumSubset(temp, target, maxVal), 1 + smallSumSubset(temp, target - data[0], maxVal)); } return 0; } // Driver code static void Main() { List<int> data = new List<int>(); data.Add(3); data.Add(1); data.Add(7); data.Add(1); data.Add(2); int target = 11; int val = smallSumSubset(data, target, data.Count + 1); if (val > data.Count) Console.Write(-1); else Console.Write(val); } } // This code is contributed by divyeshrabadiya07
Javascript
<script> // js program for the above approach // Function to find the smallest subarray // sum greater than or equal to target function smallSumSubset(data, target, maxVal) { let sum = 0; for(let i=0;i< data.length;i++) sum += data[i]; // Base Case if (target <= 0) return 0; // If sum of the array // is less than target else if (sum < target) return maxVal; // If target is equal to // the sum of the array else if (sum == target) return data.length; // Required condition else if (data[0] >= target) return 1; else if (data[0] < target) { let temp = []; for(let i = 1; i < data.length; i++) temp.push(data[i]); return Math.min(smallSumSubset(temp, target, maxVal), 1 + smallSumSubset(temp, target - data[0], maxVal)); } } // Driver Code let data = [ 3, 1, 7, 1, 2 ]; let target = 11; let val = smallSumSubset(data, target, data.length + 1); if (val > data.length) document.write( -1); else document.write(val); </script>
3
Complejidad temporal: O(2 N )
Espacio auxiliar: O(N)
Enfoque eficiente: el enfoque anterior se puede optimizar utilizando la programación dinámica memorizando los subproblemas para evitar volver a calcular.
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 subarray // with sum greater than or equal target int minlt(vector<int> arr, int target, int n) { // DP table to store the // computed subproblems vector<vector<int>> dp(arr.size() + 1 , vector<int> (target + 1, -1)); for(int i = 0; i < arr.size() + 1; i++) // Initialize first // column with 0 dp[i][0] = 0; for(int j = 0; j < target + 1; j++) // Initialize first // row with 0 dp[0][j] = INT_MAX; for(int i = 1; i <= arr.size(); i++) { for(int j = 1; j <= target; j++) { // Check for invalid condition if (arr[i - 1] > j) { dp[i][j] = dp[i - 1][j]; } else { // Fill up the dp table dp[i][j] = min(dp[i - 1][j], (dp[i][j - arr[i - 1]]) != INT_MAX ? (dp[i][j - arr[i - 1]] + 1) : INT_MAX); } } } // Print the minimum length if (dp[arr.size()][target] == INT_MAX) { return -1; } else { return dp[arr.size()][target]; } } // Driver code int main() { vector<int> arr = { 2, 3, 5, 4, 1 }; int target = 11; int n = arr.size(); cout << minlt(arr, target, n); } // This code is contributed by Surendra_Gangwar
Java
// Java program for the above approach import java.util.*; class GFG{ // Function to find the smallest subarray // with sum greater than or equal target static int minlt(int[] arr, int target, int n) { // DP table to store the // computed subproblems int[][] dp = new int[arr.length + 1][target + 1]; for(int[] row : dp) Arrays.fill(row, -1); for(int i = 0; i < arr.length + 1; i++) // Initialize first // column with 0 dp[i][0] = 0; for(int j = 0; j < target + 1; j++) // Initialize first // row with 0 dp[0][j] = Integer.MAX_VALUE; for(int i = 1; i <= arr.length; i++) { for(int j = 1; j <= target; j++) { // Check for invalid condition if (arr[i - 1] > j) { dp[i][j] = dp[i - 1][j]; } else { // Fill up the dp table dp[i][j] = Math.min(dp[i - 1][j], (dp[i][j - arr[i - 1]]) != Integer.MAX_VALUE ? (dp[i][j - arr[i - 1]] + 1) : Integer.MAX_VALUE); } } } // Print the minimum length if (dp[arr.length][target] == Integer.MAX_VALUE) { return -1; } else { return dp[arr.length][target]; } } // Driver code public static void main (String[] args) { int[] arr = { 2, 3, 5, 4, 1 }; int target = 11; int n = arr.length; System.out.print(minlt(arr, target, n)); } } // This code is contributed by offbeat
Python3
# Python3 program for the above approach import sys # Function to find the smallest subarray # with sum greater than or equal target def minlt(arr, target, n): # DP table to store the # computed subproblems dp = [[-1 for _ in range(target + 1)]\ for _ in range(len(arr)+1)] for i in range(len(arr)+1): # Initialize first # column with 0 dp[i][0] = 0 for j in range(target + 1): # Initialize first # row with 0 dp[0][j] = sys.maxsize for i in range(1, len(arr)+1): for j in range(1, target + 1): # Check for invalid condition if arr[i-1] > j: dp[i][j] = dp[i-1][j] else: # Fill up the dp table dp[i][j] = min(dp[i-1][j], \ 1 + dp[i][j-arr[i-1]]) return dp[-1][-1] # Print the minimum length if dp[-1][-1] == sys.maxsize: return(-1) else: return dp[-1][-1] # Driver Code arr = [2, 3, 5, 4, 1] target = 11 n = len(arr) print(minlt(arr, target, n))
C#
// C# program for the // above approach using System; class GFG{ // Function to find the // smallest subarray with // sum greater than or equal // target static int minlt(int[] arr, int target, int n) { // DP table to store the // computed subproblems int[,] dp = new int[arr.Length + 1, target + 1]; for(int i = 0; i < arr.Length + 1; i++) { for (int j = 0; j < target + 1; j++) { dp[i, j] = -1; } } for(int i = 0; i < arr.Length + 1; i++) // Initialize first // column with 0 dp[i, 0] = 0; for(int j = 0; j < target + 1; j++) // Initialize first // row with 0 dp[0, j] = int.MaxValue; for(int i = 1; i <= arr.Length; i++) { for(int j = 1; j <= target; j++) { // Check for invalid // condition if (arr[i - 1] > j) { dp[i, j] = dp[i - 1, j]; } else { // Fill up the dp table dp[i, j] = Math.Min(dp[i - 1, j], (dp[i, j - arr[i - 1]]) != int.MaxValue ? (dp[i, j - arr[i - 1]] + 1) : int.MaxValue); } } } // Print the minimum // length if (dp[arr.Length, target] == int.MaxValue) { return -1; } else { return dp[arr.Length, target]; } } // Driver code public static void Main(String[] args) { int[] arr = {2, 3, 5, 4, 1}; int target = 11; int n = arr.Length; Console.Write( minlt(arr, target, n)); } } // This code is contributed by gauravrajput1
Javascript
<script> // JavaScript program for the above approach // Function to find the smallest subarray // with sum greater than or equal target function minlt(arr, target, n) { // DP table to store the // computed subproblems var dp = Array.from(Array(arr.length+1), ()=>Array(target+1).fill(-1)); for(var i = 0; i < arr.length + 1; i++) // Initialize first // column with 0 dp[i][0] = 0; for(var j = 0; j < target + 1; j++) // Initialize first // row with 0 dp[0][j] = 1000000000; for(var i = 1; i <= arr.length; i++) { for(var j = 1; j <= target; j++) { // Check for invalid condition if (arr[i - 1] > j) { dp[i][j] = dp[i - 1][j]; } else { // Fill up the dp table dp[i][j] = Math.min(dp[i - 1][j], (dp[i][j - arr[i - 1]]) != 1000000000 ? (dp[i][j - arr[i - 1]] + 1) : 1000000000); } } } // Print the minimum length if (dp[arr.length][target] == 1000000000) { return -1; } else { return dp[arr.length][target]; } } // Driver code var arr = [2, 3, 5, 4, 1]; var target = 11; var n = arr.length; document.write( minlt(arr, target, n)); </script>
3
Tiempo Complejidad: O(N 2 )
Espacio Auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por saikumarkudikala y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA