Scooby and Shaggy are best of friends and also very good programmers, so they keep challenging each other with interesting

questions. Scooby gives the following question to Shaggy :

Given an array **A** consisting of **N** positive integers, what is the length of the smallest sub array of **A** whose sum

is greater than or equal to a given integer **K**. If there is no such sub array of A with sum greater than or equal to K

then return -1.

As Shaggy is preparing for his placements, he wants you to find the answer to the above question.

**Note:** A subarray is a **contiguous** part of array.

**Constraints:**

```
Number of testcases T: 1<=T<=10
Length of the array N: 1<=N<=100000
Elements of the array: 1<=A[i]<=10000
1<=K<=1000000000
```

**Input:**

```
An integer array A
An integer K
```

**Note:**

```
Your code will run against multiple testcases.
```

**Output:**

```
One integer corresponding to the length of the smallest sub array of A with sum greater than or equal to K.
If there is no such sub array with sum greater than or equal to K return -1.
```

**Examples:**

Input:

```
1 2 3 4 5
7
```

Output:

```
2
```

Explanation:

```
Following sub arrays have sum greater than or equal to given K i.e 7:
[1,2,3,4]
[1,2,3,4,5]
[2,3,4]
[2,3,4,5]
[3,4]
[3,4,5]
[4,5]
Out of these sub arrays the smallest subarray with sum greater than or equal to 7 is of length 2([3,4] or [4,5]) and hence
the answer is 2.
```

Input:

```
3 1 6 2
14
```

Output:

```
-1
```

Explanation:

```
There is no sub array with sum greater than or equal to 14
```

Input:

```
3 1 4
8
```

Output:

```
3
```

Explanation:

```
The only sub array with sum greater than or equal to 8 is the whole array [3,1,4] itself. Therefore the answer is 3.
```

NOTE:You only need to implement the given function. Do not read input, instead use the arguments to the function. Do not print the output, instead return values as specified. Still have a doubt? Checkout Sample Codes for more details.

Sign Up

to access hints and editorial solutions for**Smallest Subarray**

to access hints and editorial solutions for

Loading...