# Maximum Score From Removing Stones
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/maximum-score-from-removing-stones)
Canonical: https://scaleengineer.com/dsa/problems/maximum-score-from-removing-stones
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Data structures:** Heap (Priority Queue)
---
## Problem
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 = 6
**Output:** 6
**Explanation:** 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 = 6
**Output:** 7
**Explanation:** 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 = 8
**Output:** 8
**Explanation:** 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.

**Constraints:**

* `1 <= a, b, c <= 105`

# Approaches
## Greedy Simulation with Max-Heap
This approach simulates the game turn by turn using a greedy strategy. The core idea is that to maximize the number of moves, we should always try to balance the piles. Taking stones from the two largest piles helps reduce the disparity between the largest and smallest piles, thus allowing the game to continue for more turns. A max-heap (PriorityQueue in Java) is the ideal data structure for this simulation, as it allows for efficient retrieval of the two largest piles at each step.
**Time:** O(a + b + c). The number of iterations in the while loop is equal to the final score. The maximum possible score is `(a+b+c)/2`. Each heap operation takes O(log 3) time, which is constant. Therefore, the total time complexity is proportional to the sum of stones. · **Space:** O(1), as the priority queue will store at most three elements, which is a constant amount of space.
**Pros:** The logic is intuitive and directly follows the greedy strategy.; It's a straightforward implementation that correctly solves the problem.
**Cons:** The time complexity is proportional to the total number of stones, which can be inefficient for large inputs.; This approach might result in a 'Time Limit Exceeded' error on platforms with strict time limits, given the problem constraints.
### Explanation
The greedy strategy involves picking one stone from each of the two currently largest piles in every move. This ensures that we are always reducing the piles that are most abundant, trying to keep all three piles available for as long as possible.

We can implement this using a max-heap. A max-heap is a specialized tree-based data structure that satisfies the heap property: in a max-heap, for any given node C, if P is a parent node of C, then the value of P is greater than or equal to the value of C. This makes it very efficient to find the maximum element.

By storing the pile sizes in a max-heap, we can extract the two largest piles in `O(log k)` time, where `k` is the number of piles (here, `k=3`). We repeat this process, incrementing our score each time, until we can no longer make a move (i.e., we have fewer than two piles left).

```java
import java.util.PriorityQueue;
import java.util.Collections;

class Solution {
    public int maximumScore(int a, int b, int c) {
        // Use a max-heap to always get the two largest piles.
        // Collections.reverseOrder() makes the PriorityQueue a max-heap.
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
        if (a > 0) maxHeap.add(a);
        if (b > 0) maxHeap.add(b);
        if (c > 0) maxHeap.add(c);

        int score = 0;
        // The game continues as long as there are at least two non-empty piles.
        while (maxHeap.size() >= 2) {
            // Get the two largest piles.
            int largest = maxHeap.poll();
            int secondLargest = maxHeap.poll();

            // Perform a move.
            score++;

            // Decrement the stone counts.
            largest--;
            secondLargest--;

            // Add the piles back to the heap if they are still non-empty.
            if (largest > 0) {
                maxHeap.add(largest);
            }
            if (secondLargest > 0) {
                maxHeap.add(secondLargest);
            }
        }
        return score;
    }
}
```
### Algorithm
1. Initialize a max-priority queue and add the three pile sizes `a`, `b`, and `c` to it.
2. Initialize a variable `score` to 0.
3. Start a loop that continues as long as there are at least two piles in the priority queue (i.e., `pq.size() >= 2`).
4. Inside the loop, extract the two largest piles by polling from the priority queue twice. Let's call them `pile1` and `pile2`.
5. Increment the `score` by 1, as we are performing one move.
6. Decrement both `pile1` and `pile2` by 1 to simulate removing one stone from each.
7. If the new size of `pile1` is greater than 0, add it back to the priority queue.
8. Similarly, if the new size of `pile2` is greater than 0, add it back.
9. Once the loop terminates (fewer than two piles are left), return the total `score`.

## Mathematical Approach
A more efficient approach is to analyze the game's properties and derive a mathematical formula. By sorting the piles, we can identify two key scenarios. The relationship between the largest pile and the sum of the two smaller piles determines the maximum possible score. This avoids simulating the game step-by-step and provides an instant answer.
**Time:** O(1). Sorting three elements is a constant time operation. The rest of the algorithm involves a few comparisons and arithmetic operations. · **Space:** O(1). We only use a small, constant-size array for sorting.
**Pros:** Extremely efficient with constant time complexity.; Provides an optimal solution without any simulation.; Simple to implement once the logic is understood.
**Cons:** Requires a logical leap to understand the conditions, rather than a direct simulation.
### Explanation
Let the sorted pile sizes be `x`, `y`, and `z` such that `x <= y <= z`.

**Case 1: `x + y <= z`**
In this scenario, the largest pile `z` is greater than or equal to the sum of the other two. This means we can always use pile `z` to play against piles `x` and `y`. We can make `x` moves by pairing stones from pile `x` with stones from pile `z`. After this, pile `x` is empty. The state becomes `(0, y, z-x)`. Then, we can make `y` moves by pairing stones from pile `y` with stones from the largest pile. After this, pile `y` is also empty. The state is `(0, 0, z-x-y)`. Now, with only one non-empty pile, the game ends. The total score is the total number of moves, which is `x + y`.

**Case 2: `x + y > z`**
Here, the piles are more balanced. No single pile is larger than the sum of the other two. This condition ensures that we can always make a move as long as at least two piles are non-empty. The game is only limited by the total number of stones. Each move consumes two stones. Therefore, we can continue playing until either 0 or 1 stone is left in total. The total number of moves will be the total number of stones divided by two. The maximum score is `floor((x + y + z) / 2)`.

This logic leads to a simple and highly efficient algorithm.

```java
import java.util.Arrays;

class Solution {
    public int maximumScore(int a, int b, int c) {
        int[] piles = {a, b, c};
        Arrays.sort(piles);
        
        int x = piles[0];
        int y = piles[1];
        int z = piles[2];
        
        // Case 1: The largest pile is dominant.
        // The game is limited by the two smaller piles.
        if (x + y <= z) {
            return x + y;
        } 
        // Case 2: The piles are relatively balanced.
        // The game is limited by the total number of stones.
        else {
            return (x + y + z) / 2;
        }
    }
}
```
### Algorithm
1. Store the three pile sizes `a`, `b`, and `c` in an array.
2. Sort the array in non-decreasing order. Let the sorted sizes be `x`, `y`, and `z` where `x <= y <= z`.
3. Analyze two distinct cases:
    a. **Case 1: `x + y <= z`**. This means the largest pile is very dominant. The maximum number of moves is limited by the sum of the two smaller piles, as they will be exhausted first. The score is `x + y`.
    b. **Case 2: `x + y > z`**. This means the piles are relatively balanced. No single pile is larger than the sum of the other two. This balance allows us to make moves until almost all stones are depleted. The total number of moves is limited only by the total number of stones. Since each move removes two stones, the maximum score is `(x + y + z) / 2`.
4. Return the result based on which case is met.

# Solutions
### Java

```java
class Solution {
public
  int maximumScore(int a, int b, int c) {
    int[] s = new int[]{a, b, c};
    Arrays.sort(s);
    int ans = 0;
    while (s[1] > 0) {
      ++ans;
      s[1]--;
      s[2]--;
      Arrays.sort(s);
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int maximumScore(int a, int b, int c) {
    vector<int> s = {a, b, c};
    sort(s.begin(), s.end());
    int ans = 0;
    while (s[1]) {
      ++ans;
      s[1]--;
      s[2]--;
      sort(s.begin(), s.end());
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def maximumScore(self, a: int, b: int, c: int) -> int: s = sorted([a, b, c]) ans = 0 while s[1]: ans += 1 s[1] -= 1 s[2] -= 1 s . sort() return ans

```