Smallest subarray with sum greater than a given value

Smallest subarray with sum greater than a given value
Given an array of integers and a number x, find the smallest subarray with sum greater than the given value.
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.

A simple solution is to use two nested loops. The outer loop picks a starting element, the inner loop considers all elements (on right side of current start) as ending element. Whenever sum of elements between current start and end becomes more than the given number, update the result if current length is smaller than the smallest length so far.
Following is the implementation of simple approach.

# 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) {     //  Initilize 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 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; }

Output:3

1
4 

Time Complexity: Time complexity of the above approach is clearly O(n2).

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)     {         //  Initilize 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 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):

  

    # Initilize 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)

      

// 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 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; }

Output:

3
1
4 

How to handle negative numbers?
The above solution may not work if input array contains negative numbers. For example arr[] = {- 8, 1, 4, 2, -6}. To handle negative numbers, add a condition to ignore subarrays with negative sums.