**Problem Statement:** You are playing a solitaire game with **three piles** of stones of sizes `a`

, `b`

, and `c`

respectively. Each turn you choose two **different non-empty **piles, take one stone from each, and add `1`

point to your score. The game stops when there are **fewer than two non-empty** piles (meaning there are no more available moves).

Given three integers `a`

, `b`

, and `c`

, return *the* *maximum* **score** you can get.

**Example 1:**

Input:a = 2, b = 4, c = 6Output:6Explanation:The starting state is (2, 4, 6). One optimal set of moves is: - Take from 1st and 3rd piles, state is now (1, 4, 5) - Take from 1st and 3rd piles, state is now (0, 4, 4) - Take from 2nd and 3rd piles, state is now (0, 3, 3) - Take from 2nd and 3rd piles, state is now (0, 2, 2) - Take from 2nd and 3rd piles, state is now (0, 1, 1) - Take from 2nd and 3rd piles, state is now (0, 0, 0) There are fewer than two non-empty piles, so the game ends. Total: 6 points.

**Example 2:**

Input:a = 4, b = 4, c = 6Output:7Explanation:The starting state is (4, 4, 6). One optimal set of moves is: - Take from 1st and 2nd piles, state is now (3, 3, 6) - Take from 1st and 3rd piles, state is now (2, 3, 5) - Take from 1st and 3rd piles, state is now (1, 3, 4) - Take from 1st and 3rd piles, state is now (0, 3, 3) - Take from 2nd and 3rd piles, state is now (0, 2, 2) - Take from 2nd and 3rd piles, state is now (0, 1, 1) - Take from 2nd and 3rd piles, state is now (0, 0, 0) There are fewer than two non-empty piles, so the game ends. Total: 7 points.

**Example 3:**

Input:a = 1, b = 8, c = 8Output:8Explanation:One optimal set of moves is to take from the 2nd and 3rd piles for 8 turns until they are empty. After that, there are fewer than two non-empty piles, so the game ends.

**Solution**:

*Disclaimer*: *Don’t jump directly to the solution, try it out yourself first.*

Practice QuestionsMaximum Score From Removing Stones

**Solution 1: 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
- Extract the second largest and largest pile of stones.
- Remove them from the priority queue/heap.

- Decrease the size of both piles of stones by 1. Insert them back in the
**priority queue/heap.** - Increase
**ans**by 1.

- Return
**ans**.

**Time Complexity:** of the solution: O(k logn), where k is the answer which is how many times the while loop runs.**Space Complexity:** O(n)

#include <bits/stdc++.h> using namespace std; int maximumScore(int a, int b, int c) { // we will make a max heap and push all the elements into it priority_queue<int> basket; basket.push(a); basket.push(b); basket.push(c); int ans = 0; //make ans = 0 // we will pop the top most elements of the heap(top max element) // subtract one from each of them and insert them again in the heap, if they are not equal to 0 // we will continue the same operation until the size of the basket remains greater than 1 while (basket.size() > 1) { // taking the top 2 greater elements out of the max heap int left = basket.top(); basket.pop(); int right = basket.top(); basket.pop(); // subtracting one from each of the greatest elements left--; right--; // increasing the answer score at each iteration of the loop ans++; // if the elements that we took out are still greater than 1 after subtraction operation then we have to insert them again if (left != 0) basket.push(left); if (right != 0) basket.push(right); } //return ans return ans; }; int main() { cout << "Enter three piles of stones of sizes: " << endl; int piles1, piles2, piles3; cin >> piles1 >> piles2 >> piles3; //{4, 4, 6} cout << "There are fewer than two non-empty piles, so the game ends. Total: " << maximumScore(piles1, piles2, piles3) << " points"; }

#### Output:

There are fewer than two non-empty piles, so the game ends. Total: 7 points

*To master AlgoMaster Sheet – Maximum Score From Removing Stones in the most efficient and effective way, do check out this*:

This article is contributed by :Sayan Duttato this article oncsforall.in