Dada una array de enteros y un número x, encuentre la subarreglo más pequeña con una suma mayor que el valor dado.
Examples:
arr[] = {1, 4, 45, 6, 0, 19}
x = 51
Output: 3
Minimum length subarray is {4, 45, 6}
arr[] = {1, 10, 5, 2, 7}
x = 9
Output: 1
Minimum length subarray is {10}
arr[] = {1, 11, 100, 1, 0, 200, 3, 2, 1, 250}
x = 280
Output: 4
Minimum length subarray is {100, 1, 0, 200}
arr[] = {1, 2, 4}
x = 8
Output : Not Possible
Whole array sum is smaller than 8.
Una solución simple es usar dos bucles anidados. El ciclo externo elige un elemento inicial, el ciclo interno considera todos los elementos (en el lado derecho del inicio actual) como elemento final. Siempre que la suma de los elementos entre el inicio y el final actual sea mayor que el número dado, actualice el resultado si la longitud actual es menor que la longitud más pequeña hasta el momento.
A continuación se muestra la implementación del enfoque simple.
C++
# include <iostream>
using namespace std;
// Returns length of smallest subarray with sum greater than x.
// If there is no subarray with given sum, then returns n+1
int smallestSubWithSum(int arr[], int n, int x)
{
// Initialize length of smallest subarray as n+1
int min_len = n + 1;
// Pick every element as starting point
for (int start=0; start<n; start++)
{
// Initialize sum starting with current start
int curr_sum = arr[start];
// If first element itself is greater
if (curr_sum > x) return 1;
// Try different ending points for current start
for (int end=start+1; end<n; end++)
{
// add last element to current sum
curr_sum += arr[end];
// If sum becomes more than x and length of
// this subarray is smaller than current smallest
// length, update the smallest length (or result)
if (curr_sum > x && (end - start + 1) < min_len)
min_len = (end - start + 1);
}
}
return min_len;
}
/* Driver program to test above function */
int main()
{
int arr1[] = {1, 4, 45, 6, 10, 19};
int x = 51;
int n1 = sizeof(arr1)/sizeof(arr1[0]);
int res1 = smallestSubWithSum(arr1, n1, x);
(res1 == n1+1)? cout << "Not possible\n" :
cout << res1 << endl;
int arr2[] = {1, 10, 5, 2, 7};
int n2 = sizeof(arr2)/sizeof(arr2[0]);
x = 9;
int res2 = smallestSubWithSum(arr2, n2, x);
(res2 == n2+1)? cout << "Not possible\n" :
cout << res2 << endl;
int arr3[] = {1, 11, 100, 1, 0, 200, 3, 2, 1, 250};
int n3 = sizeof(arr3)/sizeof(arr3[0]);
x = 280;
int res3 = smallestSubWithSum(arr3, n3, x);
(res3 == n3+1)? cout << "Not possible\n" :
cout << res3 << endl;
return 0;
}
Java
class SmallestSubArraySum
{
// Returns length of smallest subarray with sum greater than x.
// If there is no subarray with given sum, then returns n+1
static int smallestSubWithSum(int arr[], int n, int x)
{
// Initialize length of smallest subarray as n+1
int min_len = n + 1;
// Pick every element as starting point
for (int start = 0; start < n; start++)
{
// Initialize sum starting with current start
int curr_sum = arr[start];
// If first element itself is greater
if (curr_sum > x)
return 1;
// Try different ending points for curremt start
for (int end = start + 1; end < n; end++)
{
// add last element to current sum
curr_sum += arr[end];
// If sum becomes more than x and length of
// this subarray is smaller than current smallest
// length, update the smallest length (or result)
if (curr_sum > x && (end - start + 1) < min_len)
min_len = (end - start + 1);
}
}
return min_len;
}
// Driver program to test above functions
public static void main(String[] args)
{
int arr1[] = {1, 4, 45, 6, 10, 19};
int x = 51;
int n1 = arr1.length;
int res1 = smallestSubWithSum(arr1, n1, x);
if (res1 == n1+1)
System.out.println("Not Possible");
else
System.out.println(res1);
int arr2[] = {1, 10, 5, 2, 7};
int n2 = arr2.length;
x = 9;
int res2 = smallestSubWithSum(arr2, n2, x);
if (res2 == n2+1)
System.out.println("Not Possible");
else
System.out.println(res2);
int arr3[] = {1, 11, 100, 1, 0, 200, 3, 2, 1, 250};
int n3 = arr3.length;
x = 280;
int res3 = smallestSubWithSum(arr3, n3, x);
if (res3 == n3+1)
System.out.println("Not Possible");
else
System.out.println(res3);
}
}
// This code has been contributed by Mayank Jaiswal
Python3
# Python3 program to find Smallest
# subarray with sum greater
# than a given value
# Returns length of smallest subarray
# with sum greater than x. If there
# is no subarray with given sum,
# then returns n+1
def smallestSubWithSum(arr, n, x):
# Initialize length of smallest
# subarray as n+1
min_len = n + 1
# Pick every element as starting point
for start in range(0,n):
# Initialize sum starting
# with current start
curr_sum = arr[start]
# If first element itself is greater
if (curr_sum > x):
return 1
# Try different ending points
# for curremt start
for end in range(start+1,n):
# add last element to current sum
curr_sum += arr[end]
# If sum becomes more than x
# and length of this subarray
# is smaller than current smallest
# length, update the smallest
# length (or result)
if curr_sum > x and (end - start + 1) < min_len:
min_len = (end - start + 1)
return min_len;
# Driver program to test above function */
arr1 = [1, 4, 45, 6, 10, 19]
x = 51
n1 = len(arr1)
res1 = smallestSubWithSum(arr1, n1, x);
if res1 == n1+1:
print("Not possible")
else:
print(res1)
arr2 = [1, 10, 5, 2, 7]
n2 = len(arr2)
x = 9
res2 = smallestSubWithSum(arr2, n2, x);
if res2 == n2+1:
print("Not possible")
else:
print(res2)
arr3 = [1, 11, 100, 1, 0, 200, 3, 2, 1, 250]
n3 = len(arr3)
x = 280
res3 = smallestSubWithSum(arr3, n3, x)
if res3 == n3+1:
print("Not possible")
else:
print(res3)
# This code is contributed by Smitha Dinesh Semwal
C#
// C# program to find Smallest
// subarray with sum greater
// than a given value
using System;
class GFG
{
// Returns length of smallest
// subarray with sum greater
// than x. If there is no
// subarray with given sum,
// then returns n+1
static int smallestSubWithSum(int []arr,
int n, int x)
{
// Initialize length of
// smallest subarray as n+1
int min_len = n + 1;
// Pick every element
// as starting point
for (int start = 0; start < n; start++)
{
// Initialize sum starting
// with current start
int curr_sum = arr[start];
// If first element
// itself is greater
if (curr_sum > x)
return 1;
// Try different ending
// points for curremt start
for (int end = start + 1;
end < n; end++)
{
// add last element
// to current sum
curr_sum += arr[end];
// If sum becomes more than
// x and length of this
// subarray is smaller than
// current smallest length,
// update the smallest
// length (or result)
if (curr_sum > x &&
(end - start + 1) < min_len)
min_len = (end - start + 1);
}
}
return min_len;
}
// Driver Code
static public void Main ()
{
int []arr1 = {1, 4, 45,
6, 10, 19};
int x = 51;
int n1 = arr1.Length;
int res1 = smallestSubWithSum(arr1,
n1, x);
if (res1 == n1 + 1)
Console.WriteLine("Not Possible");
else
Console.WriteLine(res1);
int []arr2 = {1, 10, 5, 2, 7};
int n2 = arr2.Length;
x = 9;
int res2 = smallestSubWithSum(arr2,
n2, x);
if (res2 == n2 + 1)
Console.WriteLine("Not Possible");
else
Console.WriteLine(res2);
int []arr3 = {1, 11, 100, 1, 0,
200, 3, 2, 1, 250};
int n3 = arr3.Length;
x = 280;
int res3 = smallestSubWithSum(arr3,
n3, x);
if (res3 == n3 + 1)
Console.WriteLine("Not Possible");
else
Console.WriteLine(res3);
}
}
// This code is contributed by ajit
PHP
<?php
// Returns length of smallest
// subarray with sum greater
// than x. If there is no
// subarray with given sum,
// then returns n+1
function smallestSubWithSum($arr, $n, $x)
{
// Initialize length of
// smallest subarray as n+1
$min_len = $n + 1;
// Pick every element
// as starting point
for ($start = 0; $start < $n; $start++)
{
// Initialize sum starting
// with current start
$curr_sum = $arr[$start];
// If first element
// itself is greater
if ($curr_sum > $x) return 1;
// Try different ending
// points for curremt start
for ($end= $start + 1; $end < $n; $end++)
{
// add last element
// to current sum
$curr_sum += $arr[$end];
// If sum becomes more than
// x and length of this subarray
// is smaller than current
// smallest length, update the
// smallest length (or result)
if ($curr_sum > $x &&
($end - $start + 1) < $min_len)
$min_len = ($end - $start + 1);
}
}
return $min_len;
}
// Driver Code
$arr1 = array (1, 4, 45,
6, 10, 19);
$x = 51;
$n1 = sizeof($arr1);
$res1 = smallestSubWithSum($arr1, $n1, $x);
if (($res1 == $n1 + 1) == true)
echo "Not possible\n" ;
else
echo $res1 , "\n";
$arr2 = array(1, 10, 5, 2, 7);
$n2 = sizeof($arr2);
$x = 9;
$res2 = smallestSubWithSum($arr2, $n2, $x);
if (($res2 == $n2 + 1) == true)
echo "Not possible\n" ;
else
echo $res2 , "\n";
$arr3 = array (1, 11, 100, 1, 0,
200, 3, 2, 1, 250);
$n3 = sizeof($arr3);
$x = 280;
$res3 = smallestSubWithSum($arr3, $n3, $x);
if (($res3 == $n3 + 1) == true)
echo "Not possible\n" ;
else
echo $res3 , "\n";
// This code is contributed by ajit
?>
Javascript
<script>
// Returns length of smallest subarray with sum greater than x.
// If there is no subarray with given sum, then returns n+1
function smallestSubWithSum(arr, n, x)
{
// Initialize length of smallest subarray as n+1
let min_len = n + 1;
// Pick every element as starting point
for (let start=0; start<n; start++)
{
// Initialize sum starting with current start
let curr_sum = arr[start];
// If first element itself is greater
if (curr_sum > x) return 1;
// Try different ending points for curremt start
for (let end=start+1; end<n; end++)
{
// add last element to current sum
curr_sum += arr[end];
// If sum becomes more than x and length of
// this subarray is smaller than current smallest
// length, update the smallest length (or result)
if (curr_sum > x && (end - start + 1) < min_len)
min_len = (end - start + 1);
}
}
return min_len;
}
/* Driver program to test above function */
let arr1 = [1, 4, 45, 6, 10, 19];
let x = 51;
let n1 = arr1.length;
let res1 = smallestSubWithSum(arr1, n1, x);
(res1 == n1 + 1)? document.write("Not possible<br>") :
document.write(res1 + "<br>");
let arr2 = [1, 10, 5, 2, 7];
let n2 = arr2.length;
x = 9;
let res2 = smallestSubWithSum(arr2, n2, x);
(res2 == n2 + 1)? document.write("Not possible<br>") :
document.write(res2 + "<br>");
let arr3 = [1, 11, 100, 1, 0, 200, 3, 2, 1, 250];
let n3 = arr3.length;
x = 280;
let res3 = smallestSubWithSum(arr3, n3, x);
(res3 == n3 + 1)? document.write("Not possible<br>") :
document.write(res3 + "<br>");
// This code is contributed by Surbhi Tyagi.
</script>
Producción
3 1 4
Complejidad Temporal: O(n 2 ).
Espacio Auxiliar: O(1)
Solución eficiente: este problema se puede resolver en O (n) tiempo usando la idea utilizada en esta publicación. Gracias a Ankit y Nitin por sugerir esta solución optimizada.
C++14
// O(n) solution for finding smallest subarray with sum
// greater than x
#include <iostream>
using namespace std;
// Returns length of smallest subarray with sum greater than
// x. If there is no subarray with given sum, then returns
// n+1
int smallestSubWithSum(int arr[], int n, int x)
{
// Initialize current sum and minimum length
int curr_sum = 0, min_len = n + 1;
// Initialize starting and ending indexes
int start = 0, end = 0;
while (end < n) {
// Keep adding array elements while current sum
// is smaller than or equal to x
while (curr_sum <= x && end < n)
curr_sum += arr[end++];
// If current sum becomes greater than x.
while (curr_sum > x && start < n) {
// Update minimum length if needed
if (end - start < min_len)
min_len = end - start;
// remove starting elements
curr_sum -= arr[start++];
}
}
return min_len;
}
/* Driver program to test above function */
int main()
{
int arr1[] = { 1, 4, 45, 6, 10, 19 };
int x = 51;
int n1 = sizeof(arr1) / sizeof(arr1[0]);
int res1 = smallestSubWithSum(arr1, n1, x);
(res1 == n1 + 1) ? cout << "Not possible\n"
: cout << res1 << endl;
int arr2[] = { 1, 10, 5, 2, 7 };
int n2 = sizeof(arr2) / sizeof(arr2[0]);
x = 9;
int res2 = smallestSubWithSum(arr2, n2, x);
(res2 == n2 + 1) ? cout << "Not possible\n"
: cout << res2 << endl;
int arr3[] = { 1, 11, 100, 1, 0, 200, 3, 2, 1, 250 };
int n3 = sizeof(arr3) / sizeof(arr3[0]);
x = 280;
int res3 = smallestSubWithSum(arr3, n3, x);
(res3 == n3 + 1) ? cout << "Not possible\n"
: cout << res3 << endl;
return 0;
}
Java
// O(n) solution for finding smallest subarray with sum
// greater than x
class SmallestSubArraySum {
// Returns length of smallest subarray with sum greater
// than x. If there is no subarray with given sum, then
// returns n+1
static int smallestSubWithSum(int arr[], int n, int x)
{
// Initialize current sum and minimum length
int curr_sum = 0, min_len = n + 1;
// Initialize starting and ending indexes
int start = 0, end = 0;
while (end < n) {
// Keep adding array elements while current sum
// is smaller than or equal to x
while (curr_sum <= x && end < n)
curr_sum += arr[end++];
// If current sum becomes greater than x.
while (curr_sum > x && start < n) {
// Update minimum length if needed
if (end - start < min_len)
min_len = end - start;
// remove starting elements
curr_sum -= arr[start++];
}
}
return min_len;
}
// Driver program to test above functions
public static void main(String[] args)
{
int arr1[] = { 1, 4, 45, 6, 10, 19 };
int x = 51;
int n1 = arr1.length;
int res1 = smallestSubWithSum(arr1, n1, x);
if (res1 == n1 + 1)
System.out.println("Not Possible");
else
System.out.println(res1);
int arr2[] = { 1, 10, 5, 2, 7 };
int n2 = arr2.length;
x = 9;
int res2 = smallestSubWithSum(arr2, n2, x);
if (res2 == n2 + 1)
System.out.println("Not Possible");
else
System.out.println(res2);
int arr3[]
= { 1, 11, 100, 1, 0, 200, 3, 2, 1, 250 };
int n3 = arr3.length;
x = 280;
int res3 = smallestSubWithSum(arr3, n3, x);
if (res3 == n3 + 1)
System.out.println("Not Possible");
else
System.out.println(res3);
}
}
// This code has been contributed by Mayank Jaiswal
Python3
# O(n) solution for finding smallest
# subarray with sum greater than x
# Returns length of smallest subarray
# with sum greater than x. If there
# is no subarray with given sum, then
# returns n + 1
def smallestSubWithSum(arr, n, x):
# Initialize current sum and minimum length
curr_sum = 0
min_len = n + 1
# Initialize starting and ending indexes
start = 0
end = 0
while (end < n):
# Keep adding array elements while current
# sum is smaller than or equal to x
while (curr_sum <= x and end < n):
curr_sum += arr[end]
end += 1
# If current sum becomes greater than x.
while (curr_sum > x and start < n):
# Update minimum length if needed
if (end - start < min_len):
min_len = end - start
# remove starting elements
curr_sum -= arr[start]
start += 1
return min_len
# Driver program
arr1 = [1, 4, 45, 6, 10, 19]
x = 51
n1 = len(arr1)
res1 = smallestSubWithSum(arr1, n1, x)
print("Not possible") if (res1 == n1 + 1) else print(res1)
arr2 = [1, 10, 5, 2, 7]
n2 = len(arr2)
x = 9
res2 = smallestSubWithSum(arr2, n2, x)
print("Not possible") if (res2 == n2 + 1) else print(res2)
arr3 = [1, 11, 100, 1, 0, 200, 3, 2, 1, 250]
n3 = len(arr3)
x = 280
res3 = smallestSubWithSum(arr3, n3, x)
print("Not possible") if (res3 == n3 + 1) else print(res3)
# This code is contributed by
# Smitha Dinesh Semwal
C#
// O(n) solution for finding
// smallest subarray with sum
// greater than x
using System;
class GFG {
// Returns length of smallest
// subarray with sum greater
// than x. If there is no
// subarray with given sum,
// then returns n+1
static int smallestSubWithSum(int[] arr, int n, int x)
{
// Initialize current
// sum and minimum length
int curr_sum = 0, min_len = n + 1;
// Initialize starting
// and ending indexes
int start = 0, end = 0;
while (end < n) {
// Keep adding array elements
// while current sum is smaller
// than or equal to x
while (curr_sum <= x && end < n)
curr_sum += arr[end++];
// If current sum becomes
// greater than x.
while (curr_sum > x && start < n) {
// Update minimum
// length if needed
if (end - start < min_len)
min_len = end - start;
// remove starting elements
curr_sum -= arr[start++];
}
}
return min_len;
}
// Driver Code
static public void Main()
{
int[] arr1 = { 1, 4, 45, 6, 10, 19 };
int x = 51;
int n1 = arr1.Length;
int res1 = smallestSubWithSum(arr1, n1, x);
if (res1 == n1 + 1)
Console.WriteLine("Not Possible");
else
Console.WriteLine(res1);
int[] arr2 = { 1, 10, 5, 2, 7 };
int n2 = arr2.Length;
x = 9;
int res2 = smallestSubWithSum(arr2, n2, x);
if (res2 == n2 + 1)
Console.WriteLine("Not Possible");
else
Console.WriteLine(res2);
int[] arr3
= { 1, 11, 100, 1, 0, 200, 3, 2, 1, 250 };
int n3 = arr3.Length;
x = 280;
int res3 = smallestSubWithSum(arr3, n3, x);
if (res3 == n3 + 1)
Console.WriteLine("Not Possible");
else
Console.WriteLine(res3);
}
}
// This code is contributed by akt_mit
PHP
<?php
// O(n) solution for finding
// smallest subarray with sum
// greater than x
// Returns length of smallest
// subarray with sum greater
// than x. If there is no
// subarray with given sum,
// then returns n+1
function smallestSubWithSum($arr,
$n, $x)
{
// Initialize current
// sum and minimum length
$curr_sum = 0;
$min_len = $n + 1;
// Initialize starting
// and ending indexes
$start = 0;
$end = 0;
while ($end < $n)
{
// Keep adding array elements
// while current sum is smaller
// than or equal to x
while ($curr_sum <= $x &&
$end < $n)
$curr_sum += $arr[$end++];
// If current sum becomes
// greater than x.
while ($curr_sum > $x &&
$start < $n)
{
// Update minimum
// length if needed
if ($end - $start < $min_len)
$min_len = $end - $start;
// remove starting elements
$curr_sum -= $arr[$start++];
}
}
return $min_len;
}
// Driver Code
$arr1 = array(1, 4, 45,
6, 10, 19);
$x = 51;
$n1 = sizeof($arr1);
$res1 = smallestSubWithSum($arr1,
$n1, $x);
if($res1 == $n1 + 1)
echo "Not possible\n" ;
else
echo $res1 ,"\n";
$arr2 = array(1, 10, 5, 2, 7);
$n2 = sizeof($arr2);
$x = 9;
$res2 = smallestSubWithSum($arr2,
$n2, $x);
if($res2 == $n2 + 1)
echo "Not possible\n" ;
else
echo $res2,"\n";
$arr3 = array(1, 11, 100, 1, 0,
200, 3, 2, 1, 250);
$n3 = sizeof($arr3);
$x = 280;
$res3 = smallestSubWithSum($arr3,
$n3, $x);
if($res3 == $n3 + 1)
echo "Not possible\n" ;
else
echo $res3, "\n";
// This code is contributed by ajit
?>
Javascript
<script>
// O(n) solution for finding smallest subarray with sum
// greater than x
// Returns length of smallest subarray with sum greater than
// x. If there is no subarray with given sum, then returns
// n+1
function smallestSubWithSum(arr, n, x)
{
// Initialize current sum and minimum length
let curr_sum = 0, min_len = n + 1;
// Initialize starting and ending indexes
let start = 0, end = 0;
while (end < n) {
// Keep adding array elements while current sum
// is smaller than or equal to x
while (curr_sum <= x && end < n)
curr_sum += arr[end++];
// If current sum becomes greater than x.
while (curr_sum > x && start < n) {
// Update minimum length if needed
if (end - start < min_len)
min_len = end - start;
// remove starting elements
curr_sum -= arr[start++];
}
}
return min_len;
}
/* Driver program to test above function */
let arr1 = [ 1, 4, 45, 6, 10, 19 ];
let x = 51;
let n1 = arr1.length;
let res1 = smallestSubWithSum(arr1, n1, x);
(res1 == n1 + 1) ? document.write("Not possible<br>")
: document.write(res1 + "<br>");
let arr2 = [ 1, 10, 5, 2, 7 ];
let n2 = arr2.length;
x = 9;
let res2 = smallestSubWithSum(arr2, n2, x);
(res2 == n2 + 1) ? document.write("Not possible<br>")
: document.write(res2 + "<br>");
let arr3 = [ 1, 11, 100, 1, 0, 200, 3, 2, 1, 250 ];
let n3 = arr3.length;
x = 280;
let res3 = smallestSubWithSum(arr3, n3, x);
(res3 == n3 + 1) ? document.write("Not possible<br>")
: document.write(res3 + "<br>");
// This code is contributed by subham348.
</script>
Producción
3 1 4
Complejidad temporal: O(n).
Espacio Auxiliar: O(1)
¿Cómo manejar los números negativos?
La solución anterior puede no funcionar si la array de entrada contiene números negativos. Por ejemplo arr[] = {- 8, 1, 4, 2, -6}. Para manejar números negativos, agregue una condición para ignorar los subarreglos con sumas negativas. Podemos usar la solución discutida en Encontrar subarreglo con suma dada con negativos permitidos en espacio constante
Preguntado en: Facebook
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA