El subarreglo más pequeño de un Array dado con suma mayor o igual a K | conjunto 2

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>
Producción

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>
Producción

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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *