# [Question] Subarray With Sum Closest

### Question

Given an array of integers and a number x, find the smallest subarray with sum greater than the given value.

Eg. input = (1, 4, 45, 6, 0, 19), 51, output (4, 45, 6)

### Solution

Solution 1 (the better one) is based on another question Subarray with 0 Sum. We calculate the åįžå of every number. Takes O(n) time.

If all input are positive, there can be a Solution 2 which is based on another question Subarray with Particular Sum. The sliding window search. It’s O(n) time as well.

### Code

Solution 2 (for positive input)

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