## First Approach

Two stacked loops are a straightforward solution. The outer loop chooses a starting element, while the inner loop treats all items to the right of the current start as finishing elements. If the current length is shorter than the previous shortest length, update the result whenever the sum of parts between the current start and finish exceeds the supplied number.

The basic technique is implemented as follows.

### CODE

```
# include <iostream>
using namespace std;
// Returns the length of the smallest Subarray whose sum exceeds x. If no // subarray with the supplied sum exists, returns n+1.
int smallest_SubWithSum(int arr[], int size, int x)
{
// Set the length of the smallest subarray to n+1.
int mn_ln = size + 1;
// Choose a starting position for each element.
for (int strt=0; start<size; strt++)
{
// Start the sum with the current start.
int crr_sm = arr[strt];
// If the first element is bigger,
if (crr_sm > x) return 1;
// Experiment with alternative finishing positions for the
// present start.
for (int nd=strt+1; nd<size; nd++)
{
// add the last element to the current total
crr_sm += arr[nd];
// If the total exceeds x and the length of this //subarray is
// less than the current smallest length, the smallest length should be //updated (or result)
if (crr_sm > x && (nd - strt + 1) < mn_ln)
mn_ln = (nd - strt + 1);
}
}
return mn_ln;
}
/* To test the aforementioned function, use the driver software.*/
int main()
{
int rr1[] = {1, 4, 45, 6, 10, 19};
int x_1 = 51;
int size_1 = sizeof(rr1)/sizeof(rr1[0]);
int rs1 = smallest_SubWithSum(rr1, size_1, x_1);
if(rs1 == size_1+1)
cout << "Not possible"<<endl;
else
cout << rs1 << endl;
int rr2[] = {1, 10, 5, 2, 7};
int size_2 = sizeof(rr2)/sizeof(rr2[0]);
x_2 = 9;
int rs2 = smallest_SubWithSum(rr2, size_2, x_2);
if(rs2 == size_2+1)
cout << "Not possible"<<endl;
else
cout << rs2 << endl;
int rr3[] = {1, 11, 100, 1, 0, 200, 3, 2, 1, 250};
int size_3 = sizeof(arr3)/sizeof(arr3[0]);
x_3 = 280;
int res3 = smallestSubWithSum(arr3, size_3, x_3);
if(rs3 == size_3+1)
cout << "Not possible"<<endl;
else
cout << rs3 << endl;
return 0;
}
```

#### Input

```
1, 4, 45, 6, 10, 19
51
1, 10, 5, 2, 7
9
1, 11, 100, 1, 0, 200, 3, 2, 1, 250
280
```

#### Output

```
3
1
4
```

#### Time Complexity

The time complexity of the above approach is clearly O(n2).

## Optimal Solution

This issue is O(n) time to solve. The aim is to utilize a single loop to keep track of the current total and the Subarray's start and endpoints. The following is the procedure:

### CODE

```
// O(n) solution for finding the smallest Subarray with a sum
// larger than the sum
#include <iostream>
using namespace std;
// Returns the length of the smallest Subarray whose sum exceeds the sum. // Suppose no subarray with the supplied sum exists returns size+1.
int smallestSubWithSum(int arr[], int size, int sum)
{
// Set the current sum and the minimum length.
int crr_sm = 0, mn_ln = size + 1;
// Set up the beginning and end indexes.
int strt = 0, nd = 0;
while (nd < size) {
// Continue to add array members as long as the current total // is less <=sum.
while (crr_sm <= sum && nd < size)
crr_sm += rr[nd++];
// If current sum becomes >x.
while (crr_sm > x && strt < n) {
// change min length if required
if (nd - strt < mn_ln)
mn_ln = nd - strt;
// remove start elements
crr_sm -= rr[strt++];
}
}
return mn_ln;
}
/* To test the aforementioned function, use the driver software.*/
int main()
{
int rr1[] = {1, 4, 45, 6, 10, 19};
int x_1 = 51;
int size_1 = sizeof(rr1)/sizeof(rr1[0]);
int rs1 = smallest_SubWithSum(rr1, size_1, x_1);
if(rs1 == size_1+1)
cout << "Not possible"<<endl;
else
cout << rs1 << endl;
int rr2[] = {1, 10, 5, 2, 7};
int size_2 = sizeof(rr2)/sizeof(rr2[0]);
x_2 = 9;
int rs2 = smallest_SubWithSum(rr2, size_2, x_2);
if(rs2 == size_2+1)
cout << "Not possible"<<endl;
else
cout << rs2 << endl;
int rr3[] = {1, 11, 100, 1, 0, 200, 3, 2, 1, 250};
int size_3 = sizeof(arr3)/sizeof(arr3[0]);
x_3 = 280;
int res3 = smallestSubWithSum(arr3, size_3, x_3);
if(rs3 == size_3+1)
cout << "Not possible"<<endl;
else
cout << rs3 << endl;
return 0;
}
```

#### Input

```
1, 4, 45, 6, 10, 19
51
1, 10, 5, 2, 7
9
1, 11, 100, 1, 0, 200, 3, 2, 1, 250
280
```

#### Output

```
3
1
4
```

Time Complexity

The time complexity of the above approach is clearly O(n).

## Frequently Asked Questions

#### What is a sub-array in Java?

A component or segment of an array is frequently referred to as a subarray. An array is a collection of variables defined by a programmer. Rather than generating several variables, the programmer might represent a single array with various labels.

#### What is the difference between Subarray and subsequence?

A subarray or substring must be continuous, while a subsequence does not have to be. Sequences do not have to be placed in the same order as the original sequences. However, both contiguous subsequence and Subarray are the same thing.

#### How many Subarrays are in an array?

In an array of size N, the total number of subarrays is N * (N + 1) / 2. The total number of odd continuous items in the array is equal to the number of subarrays having an odd product.

#### Are the substring and Subarray the same?

In the context of strings, a substring is the same as a subarray. For example, the substrings of the string "ara" are "a," "r," "ar," "ra," "ara," and "." Note that a substring is simply a subarray made up entirely of characters.

#### Are subsequence and substring the same?

A Substring removes characters from a string in a continuous order between two given indices. Subsequence, on the other hand, maybe created from another sequence by removing part or all of the components in between while keeping the relative order of the elements in the original sequence.

## Conclusion

So that's the end of the article Smallest subarray with a sum greater than a given value.

After reading about the Smallest Subarray with a sum greater than a given value, are you not feeling excited to read/explore more about arrays such as the __sum of two arrays__, __merge K sorted arrays__, etc. ? Don't worry; Coding Ninjas has you covered.

**Recommended problems -**

However, you may want to pursue our premium courses to give your job an advantage over the competition!

With our __Coding Ninjas Studio__ __Guided Path__, you may learn about __Data Structures and Algorithms__, Competitive Programming, __JavaScript__, System Design, and more! If you wish to test your coding abilities, check out the mock __test __series and enter the __contests __on Coding Ninjas Studio.However, suppose you've just started school and are looking for answers to concerns raised by digital behemoths such as Amazon, Microsoft, Uber, and others, as part of your placement preparations. In that case, you must evaluate the __obstacles__, __interview experiences__, and __interview package__ in this case. Please vote for our blogs if you find them valuable and exciting.

Happy studying!