Maximum Score From Removing Stones

Easy
0/40
Average time to solve is 15m
profile
Contributed by
2 upvotes
Asked in company
LinkedIn

Problem statement

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.
Detailed explanation ( Input/output format, Notes, Images )

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

Sample Input 1 :

2
5 5 5
13 10 1

Sample Output 1:

7
11

Explanation Of Sample Input 1 :

Test case 1:

We can choose pile 1 and pile 2 two times. This will make our score 2. The piles will now contain 3,3, and 5 stones respectively. We can now choose pile 1 and pile 3 two times. This will make our score 4. The piles will now contain 1,3 and 3 stones respectively. We can now choose pile 2 and pile 3 three times. This will make our score 7. The piles will now contain 1,0 and 0 stones. Since there are no two different non-empty piles of stones game comes to an end. Therefore the answer is 7.

Test case 2:

We can choose pile 1 and pile 2 ten times. This will make our score 10. The piles will now contain 3,0, and 1 stone respectively. We can now choose pile 1 and pile 3 one time. This will make our score 11. The piles will now contain 2,0 and 0 stones respectively. Since there are no two different non-empty piles of stones game comes to an end. Therefore the answer is 11.

Sample Input 2 :

2
15 1 20
13 10 3

Sample Output 2 :

16
13
Hint

Think about which two plies we should use at any instant.

Approaches (2)
Greedy Approach

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’.
Time Complexity

O((‘num1’ + ‘num2’ + ‘num3’)) where ‘num1’, ‘num2’, and ‘num3’ are the number of stones in each pile.

 

Because each time we make a move the score gets increased by 1 and the size of both piles decreases by two.

Space Complexity

O(1).

 

As we are using constant extra space.

Code Solution
(100% EXP penalty)
Maximum Score From Removing Stones
Full screen
Console