Last Updated: 10 Apr, 2021
Boxes of Power
Easy
Asked in companies
You are given a set of ‘N’ boxes. The boxes are given in the form of an array ‘gainPower’. Each box has some power associated with it. Also, you are given some initial power ‘power’. You are playing a game by choosing the boxes in such a way to maximize the total score. In one move, you can perform one of the two operations:
1. For any index ‘i’, If the current power is ‘power’, and gainPower[i] is less than or equal to ‘power’, you can lose gainPower[i] from your current power and gain 1 score and then remove it from the set of ‘N’ boxes.
2. For any index ‘i’, If the current power is ‘power’, and ‘score’ is greater than or equal to 1, you can gain gainPower[i] to your current power and lose 1 score and then remove it from the set of ‘N’ boxes.
Note:
The initial score is 0.
Each box can be used at most once.
The boxes can be used in any order.
You don’t have to remove all the boxes.
Input Format:
The first line of input contains an integer ‘T’, denoting the number of test cases. The test cases follow.
The first line contains two integers ‘N’, and ‘power’, which denotes the number of elements in the array ‘gainPower’, and the initial power you have.
The second line contains N integers denoting the elements of the array ‘gainPower’.
Output Format:
For each test case, print the maximum score you can have after choosing any number of boxes and performing any of the two operations from the boxes chosen.
Print the output of the test case in a separate line.
Note:
You are not required to print the expected output, it has already been taken care of. Just implement the function.
Constraints:
1 <= T <= 50
1 <= N <= 10^4
1 <= gainPower[i], power <= 10^4
Where ’T’ is the number of test cases, N denotes the number of elements in the array ‘gainPower’,gainPower[i] denotes the power associated with the box at index ‘i’, and power denotes the initial power you have.
Time Limit: 1 sec
Approaches
The idea is to sort the given array ‘gainPower’ and then use the two-pointer approach. Use two pointers ‘i’ and ‘j’ - one at the beginning and the other at the end of the array ‘gainPower’.
If the current power is greater than the power of the ith box, then increase the score by 1, subtract the power of the ith box from the current power and remove the box from the set. Otherwise, if the score is greater than or equal to 1, add the power of the jth box from the current power.
Algorithm:
- Initialize two integers ‘score’ to 0, ‘maxScore’ to 0, denoting the current score and the maximum score we got till now.
- Sort the given array ‘gainPower’.
- Initialize an integer ‘n’ equal to the size of the given array ‘gainPower’.
- Initialize two integers ‘i’ to 0, ‘j’ to n-1, denoting the beginning and the end of the array.
- Execute a while loop with the condition j is greater than or equal to i:
- If the current power is greater than the power of the box at index ‘i’, then subtract the power of the box at ‘i’th index from the current power, increment i by 1 as we are removing the ‘i’th box, increment the score by 1.
- Update the ‘maxScore’ as the maximum of ‘maxScore’, and ‘score’.
- Else if the current score is greater than 0, then add the power of the ‘j’th box to the current power, decrement j by 1 as we are removing the ‘j’th box, and decrement the score by 1.
- We don’t need to update the ‘maxScore’ as we are decrementing the count ie. we have already updated the earlier score in the last iteration.
- If none of the conditions holds, it means we can neither apply operation 1 nor operation 2. So, break the loop.
- Return ‘maxScore’ as the final answer.