Last Updated: 21 Aug, 2021
Raksha Bandhan
Easy
Asked in company
Ninja is celebrating Raksha Bandhan with his ‘N’ sisters. Each of his sisters plans to tie him one Rakhi, having some integer value. The integer value for all ‘N’ Rakhis is provided in an array ‘ARR’.
Ninja wants the total sum of values of all tied Rakhis to be strictly positive.
Your task is to tell him the maximum Rakhis he can have on his hand.
Example :
N = 3
ARR = [ 1, -1, 0 ]
Ninja can have Rakhi with values 1 and 0 tied to his hand so that total sum is 1.
So, we output 2 as the maximum Rakhis.
Input Format :
The first line contains an integer 'T' which denotes the number of test cases to be run. Then the test cases follow.
The first line of each test case contains integer ‘N’.
The second line contains ‘N’ space separated integers denoting the elements of array ‘ARR’.
Output format :
For each test case, print an integer denoting the maximum Rakhis Ninja can get tied.
Print the output of each test case in a new line.
Note :
You don’t need to print anything. It has already been taken care of. Just implement the given function.
Constraints :
1 <= T <= 10
1 <= N <= 10^4
-10^9 <= ARR[i] <= 10^9
Time Limit : 1 sec
Approaches
Approach :
- First, we sort the array in descending order.
- We do this because we can always take the Rakhis with positive values, and then we keep taking Rakhis till the sum remains > 0.
- Then we traverse the array from last till the sum of Rakhis selected is > 0.
Algorithm :
- Sort the input array ‘ARR’ in ascending order.
- Initialize two variables ‘sum’ and ‘ans’ to 0.
- Now iterate on the array from last i.e ‘i’ = ‘N’ - 1 to ‘i’ = 0.
- We increment ‘sum’ by ‘ARR[i]’
- If ‘sum’ ≤ 0, we break out of the loop.
- Else, we increment out ans.
- Return the ‘ans’ as the final result.
Similar problems