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.
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
An integer array A An integer K
Your code will run against multiple testcases.
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.
1 2 3 4 5 7
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.
3 1 6 2 14
There is no sub array with sum greater than or equal to 14
3 1 4 8
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.