Find out the length of the minimum subarray whose sum is greater than or equal to the given number.
This question was asked in many product-based companies coding rounds like Goldman Sachs.
Given array: [3, 1, 7, 1, 2] Given target sum: 11 Output: 3 (Minimum subarray is [3, 1, 7])
Given array=[2, 3, 5, 4, 1] Given target sum=11 Output: 3 (Minimum subarray is [3, 5, 4])
If there is no as such sub-array, return -1.
Given array=[2, 3, 2, 1, 5] Given target sum=17 Output: -1 (Target sum is greater than the sum of an array.)
This can be done using dynamic recursion.
First of all, find out all the base conditions where you don’t need recursion.
Base case conditions:
#Smallest subarray with sum greater than #or equal to the given number. def smallSumSubset(data, target, maxVal): #base condition if target<=0: return 0 elif sum(data)<target: return maxVal elif sum(data)==target: return len(data) elif data>=target: return 1 #recursive dynamic programming elif data<target: return min(smallSumSubset(data[1:], target, maxVal), \ 1+smallSumSubset(data[1:], target-data, maxVal)) data=[2, 3, 5, 4, 1] target=11 val=smallSumSubset(data, target, len(data)+1) if val>len(data): print(-1) else: print(val)
Programming concepts used in the above Python code:
This is the solution for the Smallest subarray with sum greater than given number.
Can you solve this problem in any other programming language like C, Java, etc? If you can take this challenge, submit your code in the comment. I will publish it here.