Problem Description

Given three piles of stones, represented by the integers a, b, and c, you can perform the following operation any number of times:

• Choose any two non-empty piles.
• Remove one stone from each of these two piles.
• Increase your score by 1 for each operation performed.

• Each pile's size is a non-negative integer: 0 ≤ a, b, c ≤ 10^5
• You must always choose two different non-empty piles.

Thought Process

At first, one might consider simulating the process: repeatedly picking the two largest non-empty piles and removing one stone from each, counting each operation. However, this brute-force approach would be inefficient for large input sizes.

To optimize, we need to recognize that the only thing that matters is the number of stones in each pile and the rule that you can only remove stones from two different non-empty piles at a time. The operation is not dependent on the order, but on the counts.

The main insight is that the process should continue until one or two piles become empty. The maximum number of operations is limited by both the total number of stones and the largest pile: you can't make more moves than half the total number of stones (since each move removes two stones), and you can't continue once the largest pile is depleted by the other two.

Solution Approach

Let's break down the algorithm step-by-step:

1. Sort the pile sizes: Consider the three piles as x, y, z such that x ≤ y ≤ z.
2. Key Observations:
   • If the largest pile (z) has more stones than the sum of the other two (x + y), then the maximum number of moves is x + y. This is because after x + y moves, the two smaller piles will be empty, and no more moves can be made.
   • Otherwise, the maximum number of moves is limited by half the total number of stones, i.e., (x + y + z) // 2. This is because each move removes two stones, and you can't remove more stones than are present.
3. Algorithm:
   • Calculate the sum total = a + b + c.
   • Find the maximum of the three piles: max_pile = max(a, b, c).
   • Return min(total // 2, total - max_pile) as the answer.

Example Walkthrough

Example Input: a = 2, b = 4, c = 6
Step-by-step:

• Sort piles: 2, 4, 6 (already sorted)
• Total stones: 2 + 4 + 6 = 12
• Max pile: 6
• Check if 6 > 2 + 4? No (6 = 6), so use total // 2 = 6
• So, the maximum score is 6

1. Remove from piles with 6 and 4: [2, 3, 5] (score: 1)
2. Remove from 5 and 3: [2, 2, 4] (score: 2)
3. Remove from 4 and 2: [1, 2, 3] (score: 3)
4. Remove from 3 and 2: [1, 1, 2] (score: 4)
5. Remove from 2 and 1: [0, 1, 1] (score: 5)
6. Remove from last two non-empty: [0, 0, 0] (score: 6)

Time and Space Complexity

Brute-force Approach:

• Each operation removes two stones, so up to O(a + b + c) iterations.
• Each iteration requires finding the two largest piles, which is O(1) for three piles, but still inefficient for large pile sizes.

• Only a constant number of operations (sorting three numbers, finding max, sum, and min), so O(1) time complexity.
• Space complexity is also O(1) as no extra space is used.

Summary

The key insight for this problem is realizing that the maximum number of moves is constrained by both the total number of stones and the size of the largest pile. By using the formula min((a + b + c) // 2, a + b + c - max(a, b, c)), we can compute the answer in constant time. This makes the solution both elegant and highly efficient, avoiding unnecessary simulation or iteration.

Code Implementation

class Solution:
    def maximumScore(self, a: int, b: int, c: int) -> int:
        total = a + b + c
        max_pile = max(a, b, c)
        return min(total // 2, total - max_pile)
      

class Solution {
public:
    int maximumScore(int a, int b, int c) {
        int total = a + b + c;
        int max_pile = std::max({a, b, c});
        return std::min(total / 2, total - max_pile);
    }
};
      

class Solution {
    public int maximumScore(int a, int b, int c) {
        int total = a + b + c;
        int max_pile = Math.max(a, Math.max(b, c));
        return Math.min(total / 2, total - max_pile);
    }
}
      

var maximumScore = function(a, b, c) {
    const total = a + b + c;
    const max_pile = Math.max(a, b, c);
    return Math.min(Math.floor(total / 2), total - max_pile);
};