Lucky Ninja

Easy
0/40
Average time to solve is 15m
profile
Contributed by
2 upvotes
Asked in company
OYO

Problem statement

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.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1 :
2
5 -10
10 2 -2 -20 10
6 33
9 4 20 3 10 15
Sample Output 1 :
7
15
Explanation of Sample Input 1 :
Test Case 1 :
For the first test case, given ‘ARR’ is [ 10, 2, -2, -20, 10 ] and ‘K’ is ‘-10'.  So, we return ‘5’ as we can choose continuous items (subarray) like ‘ARR’[3], ‘ARR’[0...3], ‘ARR’[1...3], ‘ARR’[2...3], ‘ARR’[1...4], ‘ARR’[2...4], ‘ARR’[3...4] as the sum of values of items in these subarrays is less than or equal to -10.

Test Case 2 :
For this test case, given ‘ARR’ is [ 9, 4, 20, 3, 10, 15 ] and ‘K’ is ‘33’. So we return ‘2’ i.e. subarray ‘ARR’[0], ‘ARR’[1], ‘ARR’[2], ‘ARR’[3], ‘ARR’[4], ‘ARR’[5], ‘ARR’[0...1], ‘ARR’[0...2], ‘ARR’[1...2], ‘ARR’[1...3], ‘ARR’[2...3], ‘ARR’[2...4], ‘ARR’[3...4], ‘ARR’[3...5], ‘ARR’[4...5].
Sample Input 2 :
2
5 6
10 -4 6 2 -8
6 11
9 2 4 2 -6
Sample Output 2 :
11
13
Hint

Can you find the sum of every subarray?

Approaches (3)
Brute Force Approach

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’.
Time Complexity

O(N^2), where ‘N’ is the size of the given array.

 

As we are traversing the ‘ARR’ for each and every index, so overall complexity becomes equal to O(N ^ 2).

Space Complexity

O(1).

 

As we are using the constant space.

Code Solution
(100% EXP penalty)
Lucky Ninja
Full screen
Console