Last Updated: 9 Apr, 2021
Maximum Score From Removing Stones
Easy
Asked in company
You have been given three piles of stones of size ‘num1’, ‘num2’, and ‘num3’. In each turn, you can choose two different non-empty piles of stones and remove one stone from each pile and increase your score by 1 point. The game stops when there are fewer than two non-empty piles of stones. Return the maximum score you can get.
Example :
Let’s say you have three piles of stones of sizes 3, 4, and 2 respectively.
We can choose pile 1 and pile 2 three times. This will make our score 3. The piles will now contain 0, 1, and 2 stones respectively. We can now choose pile 2 and pile 3 one time. This will make our score 4. The piles will now contain 0, 0, and 1 stone respectively. Since there are no two different non-empty piles of stones game comes to an end. Therefore the answer is 4.
Input Format :
The first line contains a single integer ‘T’ representing the number of test cases. The 'T' test cases follow.
The only line of each test case contains three space-separated integers ‘num1’,’num2’, and ‘num3’ representing the size of three piles of stones for which you need to return the maximum score.
Output Format :
For each test case, print an integer denoting the maximum score you can get.
Note :
You do not need to print anything; it has already been taken care of. Just implement the function.
Constraints :
1 <= T <= 10000
1 <= ‘num1’ <= 10^5
1 <= ‘num2’ <= 10^5
1 <= ‘num3’ <= 10^5
Time Limit: 1sec
Approaches
As we need to maximize the score we need to think greedily. At every move, we will always choose the pile with the maximum number of stones and the pile with the second maximum number of stones. This approach will always lead to the maximum score. We can use a priority queue/heap to implement this approach :
- Declare ‘ans’ and initialize it with zero.
- Insert size of three piles of stones in a priority queue/heap.
- Run a loop till the priority queue/heap contains only one pile with non zero stones left:-
- Extract the second largest and largest pile of stones.
- Remove them from the priority queue/heap.
- If the size of second-largest pile is zero break out of the loop.
- Increase ‘ans’ by 1.
- Decrease the size of both piles of stones by 1. Insert them back in the priority queue/heap.
- Return ‘ans’.
We can implement the approach as follows:
- Declare ‘ans’ and initialize it with zero.
- We can break it into two cases:-
- If the size of the largest pile of stones is greater than the sum of the other two piles of stones, the answer will be the sum of the two smaller piles. For example:- ‘num1’ = 13, ‘num2’ = 10 and ‘num3’ = 1. Then the answer will be 11.
- Else initialize ‘ans’ with (‘num1’ + ‘num2’ + ‘num3’)/2. For example:- ‘num1’ = 10, ‘num2’ = 10 and ‘num3’ = 2. Then the answer will be 11.
- Return ‘ans’.