Maximum Score From Removing Stones — Medium Problem & Solution

Problem statement

Three piles hold a, b and c stones. On each turn you pick two different non-empty piles and remove one stone from each, scoring one point.

Play until fewer than two piles are non-empty. Return the maximum score you can reach.

Example 1

Input: a = 2, b = 4, c = 6
Output: 6
Explanation: The two smaller piles together match the biggest, so every stone can be paired off.

Example 2

Input: a = 4, b = 4, c = 6
Output: 7
Explanation: Fourteen stones, so seven pairs.

Example 3

Input: a = 1, b = 8, c = 8
Output: 8
Explanation: The two 8-piles carry the game; one stone is stranded.

Constraints

• 1 <= a, b, c <= 10^5

How to solve Maximum Score From Removing Stones

Two cases. If the biggest pile exceeds the sum of the other two, every turn must use it, so the score is that sum. Otherwise the piles can be balanced and the score is ⌊(a + b + c) / 2⌋.

Approach

1. Let mx be the largest pile and rest the sum of the other two.
2. If rest < mx, return rest.
3. Otherwise return (a + b + c) / 2, rounded down.

Why it works

The first case is a hard ceiling: every turn consumes one stone from a pile other than the biggest, so the other two piles run out after rest turns. In the second case no pile can ever outgrow the rest, so a stone is stranded only when the total is odd — hence the floor. Simulating with a heap (always take from the two largest piles) reaches the same answer, more slowly.

Complexity

• Time — O(1)
• Space — O(1)

Pitfalls

• Always answering (a + b + c) / 2 overshoots when one pile dominates.
• Always answering rest undershoots a balanced set of piles.
• The division rounds down; an odd total strands one stone.

Reference solution

Python

def maximumScore(a: int, b: int, c: int) -> int:
    total = a + b + c
    mx = max(a, b, c)
    rest = total - mx
    return rest if rest < mx else total // 2

JavaScript

var maximumScore = function(a, b, c) {
    var total = a + b + c;
    var mx = Math.max(a, Math.max(b, c));
    var rest = total - mx;
    return rest < mx ? rest : Math.floor(total / 2);
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More math problems

• Find the Winner of the Circular Game Medium
• Stone Game VII Medium
• Number of Ways to Divide a Long Corridor Medium
• Count Ways to Group Overlapping Ranges Medium
• Count Number of Ways to Place Houses Medium
• Count Number of Texts Medium