Maximum Score From Removing Stones

Medium
960.

Maximum Score From Removing Stones

MediumMathGreedyHeap (Priority Queue)AmazonGoogleZoho

Maximum Score From Removing Stones is a medium coding problem on math, greedy and heap, asked in Amazon, Google and Zoho interviews.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} a
 * @param {number} b
 * @param {number} c
 * @return {number}
 */
var maximumScore = function(a, b, c) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Maximum Score From Removing Stones — Problem & Solution

Maximum Score From Removing Stones solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Maximum Score From Removing Stones is a medium coding problem on math, greedy and heap, asked in Amazon, Google and Zoho interviews.

  • Difficulty: Medium
  • Topics: Math, Greedy, Heap
  • Asked at: Amazon, Google, Zoho
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

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

Hints for Maximum Score From Removing Stones

  1. Hint 1

    Each turn removes exactly two stones, so the score is half the stones removed.

  2. Hint 2

    If the largest pile is bigger than the other two combined, it is the bottleneck.

  3. Hint 3

    Otherwise everything can be paired off, up to one leftover stone.

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

Java

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

C++

int maximumScore(int a, int b, int c) {
    int total = a + b + c;
    int mx = max(a, max(b, c));
    int rest = total - mx;
    return rest < mx ? rest : 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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 337 math problems · the whole catalogue

Learn the technique: Greedy Algorithms · Heaps and Priority Queues