Last Updated: 27 Apr, 2021
Lucky Ninja
Easy
Asked in company
One day Ninja participates in the ‘chit fund’ lottery contest and wins a chance to collect some exciting prizes. There is some value attached to each of the 'N' items and is present in the form of an array 'ARR'. Now Ninja has been given some value 'K' and he can choose the items from the 'ARR' in a continuous manner such that the sum of those items is at most 'K'.
Ninja wants to know how many possible combinations of continuous items he can pick.
So your task is to help Ninja in counting the total number of combinations of continuous items he can choose from 'ARR' such that the sum of values of items in these combinations is at most 'K'.
For Example :
Suppose the given 'ARR' is [ 2, -1, 3, 5, 2 ], and the value 'K' is given to ninja is ‘7’.
So we return ‘10’ as the answer. i.e. ‘ARR’[0], ‘ARR’[1], ‘ARR’[2], ‘ARR’[3], ‘ARR’[4], ‘ARR’[0...1], ‘ARR’[0...2], ‘ARR’[1...2], ‘ARR’[1...3], ‘ARR’[3...4].
Note :
You are not required to print anything explicitly. It has already been taken care of. Just implement the function.
Input Format :
The first line of input contains a ‘T’ number of test cases. Then ‘T’ line follows:
The first line of each test case contains two integers input ‘N’ and ‘K’ i.e size of the array 'ARR' and the given value of the sum.
The second line of each test case contains 'N' single-spaced integers denoting the elements of 'ARR'.
Output Format :
For each test case, return the total number of possible combinations.
Constraints :
1 <= T <= 500
1 <= N <= 1000
-10 ^ 3 <= ARR[i], K <=10 ^ 3
Where ‘ARR[i]’ represents the value of the 'ith' item.
Time Limit: 1 second
Approaches
The idea here is to traverse all the subarrays and calculate their sum. If the sum is equal or less than the required sum then increment the count of subarrays.
Algorithm
- Declare a variable ‘ANS’ for storing the count of the possible subarrays.
- Run a loop where ‘i’ starts from ‘0’ to ‘N’:
- Declare a variable ‘SUM’ and initialize it with ‘0’.
- Run another loop where ‘j’ starts from ‘i’ up to ‘N’:
- Find the ‘SUM’ of each subarray.
- Check if ‘SUM ≤ K’.
- If so, include the current subarray in the answer, so ‘ANS = ANS +1’.
- Now return the ‘ANS’.
The idea here is to use the multiset and store the value of the current sum in it. So whenever we find there is a difference between the current sum value and the given sum we check values less than already present in our multiset and increment the final answer by that count.
Algorithm
- Firstly we declare a multiset ‘SORTED_ARR’ for storing the current sum in it.
- Now we declare two variables ‘CUR’ and ‘ANS’ for storing the current value of sum and the final answer respectively.
- Now run a loop where ‘i’ starts from ‘0’ to ‘N’:
- Increase the ‘CUR’ as ‘CUR += ARR[i]’.
- We take the difference in ‘DIFF’ as ‘DIFF = CUR - K’.
- Starting from the first index of ‘SORTED_ARR’ we traverse and store the count of elements that are smaller than ‘DIFF’.
- Increase the ‘ANS’ by the count of those numbers which are smaller than ‘DIFF’.
- Now we push the ‘CUR’ in our ‘SORTED_ARR’.
- Return the ‘ANS’.
The idea here is to use the concept of ‘Fenwick Tree’. So whenever we find that there is a difference between the current sum value and the given sum we, with the help of ‘Fenwick Tree’, find the count of those elements and add them in the final answer.
Algorithm
- Firstly we declare a vector for storing the elements according to the binary index tree.
- Now we declare two variables ‘CUR’ and ‘ANS’ for storing the current value of sum and the final answer respectively.
- Now run a loop where ‘i’ starts from ‘0’ to ‘N’.
- Now increase the ‘CUR’ as ‘CUR += ARR[i]’.
- Now we take the difference in ‘DIFF’ as ‘DIFF = CUR - K’
- Now for finding the count of a smaller number we just simply call the query method of ‘Fenwick Tree’.
- Increase the ‘ANS’ by the count of those numbers which are smaller than ‘DIFF’.
- Now we update the current sum by calling the ‘Update’ method of ‘Fenwick Tree’.
- Return the ‘ANS’.
Similar problems