Dada una array, arr[] de tamaño N , dos enteros positivos K y S , la tarea es encontrar la longitud del subarreglo más pequeño de tamaño mayor que K , cuya suma es mayor que S .
Ejemplos:
Entrada: arr[] = {1, 2, 3, 4, 5}, K = 1, S = 8
Salida: 2
Explicación:
el subarreglo más pequeño con suma mayor que S(=8) es {4, 5}
Por lo tanto, el la salida requerida es 2.Entrada: arr[] = {1, 3, 5, 1, 8, 2, 4}, K= 2, S= 13
Salida: 3
Enfoque: El problema se puede resolver utilizando la Técnica de la Ventana Deslizante . Siga los pasos a continuación para resolver el problema:
- Inicialice dos variables, digamos, i = 0 y j = 0 , ambas apuntando al inicio de la array, es decir, el índice 0.
- Inicialice una suma variable para almacenar la suma del subArray que se está procesando actualmente.
- Atraviese la array , arr[] y aumentando j y agregando arr[j]
- Tome nuestra longitud de la ventana o la longitud del subArray actual que está dada por j-i+1 (+1 porque los índices comienzan desde cero) .
- En primer lugar, verifique si el tamaño del subArray actual, es decir, winLen aquí, es mayor que K . si este no es el caso, incremente el valor de j y continúe el bucle.
- De lo contrario, obtenemos que el tamaño del Subarreglo actual es mayor que K , ahora tenemos que verificar si cumplimos con la segunda condición, es decir, la suma del Subarreglo actual es mayor que S.
- Si este es el caso, actualizamos la variable minLength que almacena la longitud mínima del subArray que cumple con las condiciones anteriores.
- En este momento, verificamos si el tamaño del subArray se puede reducir (incrementando i ) de modo que aún sea mayor que K y la suma también sea mayor que S. Constantemente eliminamos el i-ésimo elemento de la array de la suma para reducir el tamaño del subArray en el ciclo While y luego incrementamos j de tal manera que nos movemos al siguiente elemento en el arreglo.
- Finalmente, imprima la longitud mínima del subarreglo requerido obtenido que satisfaga las condiciones.
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 to find the length of the smallest subarray of
// size > K with sum greater than S
int smallestSubarray(int K, int S, int arr[], int N)
{
// Store the first index of the current subarray
int start = 0;
// Store the last index of the current subarray
int end = 0;
// Store the sum of the current subarray
int currSum = arr[0];
// Store the length of the smallest subarray
int res = INT_MAX;
while (end < N - 1) {
// If sum of the current subarray <= S or length of
// current subarray <= K
if (currSum <= S || (end - start + 1) <= K) {
// Increase the subarray sum and size
currSum += arr[++end];
}
else {
// Update to store the minimum size of subarray
// obtained
res = min(res, end - start + 1);
// Decrement current subarray size by removing
// first element
currSum -= arr[start++];
}
}
// Check if it is possible to reduce the length of the
// current window
while (start < N) {
if (currSum > S && (end - start + 1) > K)
res = min(res, (end - start + 1));
currSum -= arr[start++];
}
return res;
}
// Driver Code
int main()
{
int arr[] = { 1, 2, 3, 4, 5 };
int K = 1, S = 8;
int N = sizeof(arr) / sizeof(arr[0]);
cout << smallestSubarray(K, S, arr, N);
}
// This code is contributed by Sania Kumari Gupta
C
// C program to implement the above approach
#include <limits.h>
#include <stdio.h>
// Find minimum between two numbers.
int min(int num1, int num2)
{
return (num1 > num2) ? num2 : num1;
}
// Function to find the length of the smallest subarray of
// size > K with sum greater than S
int smallestSubarray(int K, int S, int arr[], int N)
{
// Store the first index of the current subarray
int start = 0;
// Store the last index of the current subarray
int end = 0;
// Store the sum of the current subarray
int currSum = arr[0];
// Store the length of the smallest subarray
int res = INT_MAX;
while (end < N - 1) {
// If sum of the current subarray <= S or length of
// current subarray <= K
if (currSum <= S || (end - start + 1) <= K) {
// Increase the subarray sum and size
currSum += arr[++end];
}
else {
// Update to store the minimum size of subarray
// obtained
res = min(res, end - start + 1);
// Decrement current subarray size by removing
// first element
currSum -= arr[start++];
}
}
// Check if it is possible to reduce the length of the
// current window
while (start < N) {
if (currSum > S && (end - start + 1) > K)
res = min(res, (end - start + 1));
currSum -= arr[start++];
}
return res;
}
// Driver Code
int main()
{
int arr[] = { 1, 2, 3, 4, 5 };
int K = 1, S = 8;
int N = sizeof(arr) / sizeof(arr[0]);
printf("%d", smallestSubarray(K, S, arr, N));
}
// This code is contributed by Sania Kumari Gupta
Java
// Java program to implement
// the above approach
import java.io.*;
class GFG{
// Function to find the length of the
// smallest subarray of size > K with
// sum greater than S
public static int smallestSubarray(int k, int s,
int[] array, int N)
{
int i=0;
int j=0;
int minLen = Integer.MAX_VALUE;
int sum = 0;
while(j < N)
{
sum += array[j];
int winLen = j-i+1;
if(winLen <= k)
j++;
else{
if(sum > s)
{
minLen = Math.min(minLen,winLen);
while(sum > s)
{
sum -= array[i];
i++;
}
j++;
}
}
}
return minLen;
}
// Driver Code
public static void main(String[] args)
{
int[] arr = { 1, 2, 3, 4, 5 };
int K = 1, S = 8;
int N = arr.length;
System.out.print(smallestSubarray(K, S, arr, N));
}
}
// This code is contributed by akhilsaini
Python3
# Python3 program to implement # the above approach import sys # Function to find the length of the # smallest subarray of size > K with # sum greater than S def smallestSubarray(K, S, arr, N): # Store the first index of # the current subarray start = 0 # Store the last index of # the current subarray end = 0 # Store the sum of the # current subarray currSum = arr[0] # Store the length of # the smallest subarray res = sys.maxsize while end < N - 1: # If sum of the current subarray <= S # or length of current subarray <= K if ((currSum <= S) or ((end - start + 1) <= K)): # Increase the subarray # sum and size end = end + 1; currSum += arr[end] # Otherwise else: # Update to store the minimum # size of subarray obtained res = min(res, end - start + 1) # Decrement current subarray # size by removing first element currSum -= arr[start] start = start + 1 # Check if it is possible to reduce # the length of the current window while start < N: if ((currSum > S) and ((end - start + 1) > K)): res = min(res, (end - start + 1)) currSum -= arr[start] start = start + 1 return res; # Driver Code if __name__ == "__main__": arr = [ 1, 2, 3, 4, 5 ] K = 1 S = 8 N = len(arr) print(smallestSubarray(K, S, arr, N)) # This code is contributed by akhilsaini
C#
// C# program to implement
// the above approach
using System;
class GFG{
// Function to find the length of the
// smallest subarray of size > K with
// sum greater than S
static int smallestSubarray(int K, int S,
int[] arr, int N)
{
// Store the first index of
// the current subarray
int start = 0;
// Store the last index of
// the current subarray
int end = 0;
// Store the sum of the
// current subarray
int currSum = arr[0];
// Store the length of
// the smallest subarray
int res = int.MaxValue;
while (end < N - 1)
{
// If sum of the current subarray <= S
// or length of current subarray <= K
if (currSum <= S ||
(end - start + 1) <= K)
{
// Increase the subarray
// sum and size
currSum += arr[++end];
}
// Otherwise
else
{
// Update to store the minimum
// size of subarray obtained
res = Math.Min(res, end - start + 1);
// Decrement current subarray
// size by removing first element
currSum -= arr[start++];
}
}
// Check if it is possible to reduce
// the length of the current window
while (start < N)
{
if (currSum > S && (end - start + 1) > K)
res = Math.Min(res, (end - start + 1));
currSum -= arr[start++];
}
return res;
}
// Driver Code
static public void Main()
{
int[] arr = { 1, 2, 3, 4, 5 };
int K = 1, S = 8;
int N = arr.Length;
Console.Write(smallestSubarray(K, S, arr, N));
}
}
// This code is contributed by akhilsaini
Javascript
<script>
// JavaScript program to implement
// the above approach
// Function to find the length of the
// smallest subarray of size > K with
// sum greater than S
function smallestSubarray(K, S, arr, N)
{
// Store the first index of
// the current subarray
let start = 0;
// Store the last index of
// the current subarray
let end = 0;
// Store the sum of the
// current subarray
let currSum = arr[0];
// Store the length of
// the smallest subarray
let res = Number.MAX_SAFE_INTEGER;
while (end < N - 1)
{
// If sum of the current subarray <= S
// or length of current subarray <= K
if (currSum <= S
|| (end - start + 1) <= K)
{
// Increase the subarray
// sum and size
currSum += arr[++end];
}
// Otherwise
else {
// Update to store the minimum
// size of subarray obtained
res = Math.min(res, end - start + 1);
// Decrement current subarray
// size by removing first element
currSum -= arr[start++];
}
}
// Check if it is possible to reduce
// the length of the current window
while (start < N)
{
if (currSum > S
&& (end - start + 1) > K)
res = Math.min(res, (end - start + 1));
currSum -= arr[start++];
}
return res;
}
// Driver Code
let arr = [ 1, 2, 3, 4, 5 ];
let K = 1, S = 8;
let N = arr.length;
document.write(smallestSubarray(K, S, arr, N));
// This code is contributed by Surbhi tyagi.
</script>
Producción:
2
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por kholiyagaurav121 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA