Raksha Bandhan

Easy

0/40

Contributed by

70 upvotes

Asked in company

Problem statement

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.

Detailed explanation ( Input/output format, Notes, Images )

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

Sample Input 1 :

Sample Output 1 :

1
3

Explanation Of Sample Input 1 :

For test case 1 we have, 
If we try to get both Rakhis tied, we get sum = 0. So, we only can use Rakhi with the value of 3 to get a positive sum. Hence, we output 1.

For test case 2 we have,
If we try to get all 3 Rakhis tied, the total sum is 1. Hence, we output 3.

Sample Input 2 :

Sample Output 2 :

2
2
0

Hint 1

Think about sorting the array.

Approaches (1)

Approach 1

Greedy Approach

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.

Time Complexity

O(N*logN) , where ‘N’ is the length of the array ‘ARR’.

Since we are sorting the array, the overall time complexity is O(N*logN).

Space Complexity

O(1)

Constant extra space is required. Hence, the overall Space Complexity is O(1).

(100% EXP penalty)

Raksha Bandhan

Console