Boxes of Power

Easy
0/40
Average time to solve is 20m
profile
Contributed by
3 upvotes
Asked in companies
WalmartMedia.netUber

Problem statement

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.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1:
2
4 100
50 300 100 200
4 100
50 50 50 50
Sample Output 1:
2
2
Explanation for Sample Input 1:
In the first test case, there are 4 boxes with power [50, 300, 100, 200]. You have initial power = 100 and initial score = 0. We can follow the following steps to maximize the score:

    Apply operation 1 on the box with power = 50. After applying the operation, gainPower = [300, 100, 200], power = 50, score = 1.
    Apply operation 2 on the box with power = 300. 

After applying the operation, gainPower = [100, 200], power = 350, score = 0.

    Apply operation 1 on the box with power = 100. After applying the operation, gainPower = [200], power = 250, score = 1.

    Apply operation 1 on the box with power = 200. After applying the operation, gainPower = [], power = 50, score = 2.

Hence, the answer is 2.

In the second test case, there are 4 boxes with power [50, 50, 50, 50]. You have initial power = 100 and initial score = 0. We can follow the following steps to maximize the score:

    Apply operation 1 on the first box with power = 50. After applying the operation, gainPower = [50, 50, 50], power = 50, score = 1.

    Apply operation 1 on the second box with power = 50. After applying the operation, gainPower = [50, 50], power = 0, score = 2.

Now, you can also apply operation 2 in other boxes but the maximum score you can get is 2. Hence, the answer is 2.
Sample Input 2:
2
8 500
100 200 300 400 500 600 700 800 
3 500
100 200 300
Sample Output 2:
3
2
Hint

Can you use the two-pointer approach to find the answer?

Approaches (1)
Two Pointers

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.

 

Time Complexity

O(N*log(N)), where N is the number of boxes given.

 

As we are sorting the array ‘gainPower’ which takes O(N*log(N)) time. Hence, the overall time complexity is O(N*log(N)).


 

Space Complexity

O(1), as we are using constant space.


 

Code Solution
(100% EXP penalty)
Boxes of Power
Full screen
Console