Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/1753.html
1753. Maximum Score From Removing Stones
Level
Medium
Description
You are playing a solitaire game with three piles of stones of sizes a
, b
, and c
respectively. Each turn you choose two different nonempty piles, take one stone from each, and add 1
point to your score. The game stops when there are fewer than two nonempty 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 nonempty 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 nonempty 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 nonempty piles, so the game ends.
Constraints:
1 <= a, b, c <= 10^5
Solution
Use a greedy approach. Use a priority queue to store the three pile sizes, where the maximum element is polled first. Offer a
, b
, and c
to the priority queue. While the priority queue has at least 2 elements, poll 2 elements, decrease them by 1, and offer them back to the priority queue if they are greater than 0. Each time increase the score by 1. Finally, return the score.

class Solution { public int maximumScore(int a, int b, int c) { int score = 0; PriorityQueue<Integer> priorityQueue = new PriorityQueue<Integer>(new Comparator<Integer>() { public int compare(Integer num1, Integer num2) { return num2  num1; } }); priorityQueue.offer(a); priorityQueue.offer(b); priorityQueue.offer(c); while (priorityQueue.size() > 1) { int num1 = priorityQueue.poll()  1; int num2 = priorityQueue.poll()  1; score++; if (num1 > 0) priorityQueue.offer(num1); if (num2 > 0) priorityQueue.offer(num2); } return score; } } ############ class Solution { public int maximumScore(int a, int b, int c) { int[] s = new int[] {a, b, c}; Arrays.sort(s); if (s[0] + s[1] < s[2]) { return s[0] + s[1]; } return (a + b + c) >> 1; } }

class Solution: def maximumScore(self, a: int, b: int, c: int) > int: a, b, c = sorted([a, b, c]) if a + b < c: return a + b return (a + b + c) >> 1 ############ # 1753. Maximum Score From Removing Stones # https://leetcode.com/problems/maximumscorefromremovingstones from heapq import heappush, heappop, heapify class Solution: # heap def maximumScore(self, a: int, b: int, c: int) > int: res = 0 stones = [a,b,c] heapify(stones) while abs(stones[0]) > 0 and abs(stones[1]) > 0: first = heappop(stones) + 1 second = heappop(stones) + 1 heappush(stones, first) heappush(stones, second) res += 1 return res # reverse engineering / math def maximumScore(self, a: int, b: int, c: int) > int: return min((a+b+c)//2 , a+b+c  max(a,b,c))

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

func maximumScore(a int, b int, c int) int { s := []int{a, b, c} sort.Ints(s) if s[0]+s[1] < s[2] { return s[0] + s[1] } return (a + b + c) >> 1 }