We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Maximum Score From Removing Stones

Difficulty: Medium

Problem 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 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. Given three integers a, b, and c, return the maximum score you can get.

Key Insights

  • The score is maximized by always removing stones from the two largest piles.
  • The game ends when fewer than two piles are non-empty, which means we need to carefully manage the distribution of stones.
  • If one pile is significantly larger than the others, it can only contribute to the score until the smaller piles are exhausted.

Space and Time Complexity

Time Complexity: O(1)
Space Complexity: O(1)

Solution

To solve this problem, we can use a greedy approach. The idea is to keep removing stones from the two largest piles until we can no longer do so. We can achieve this by sorting the piles and continuously updating their sizes. The maximum score can be calculated as the minimum of the sum of all stones divided by 2 and the sum of the two largest piles. This ensures that we do not exceed the available stones while maximizing the moves.

Code Solutions

def maximumScore(a: int, b: int, c: int) -> int:
    # Sort the piles
    piles = sorted([a, b, c])
    # The maximum score is the minimum of half the total stones and the sum of the two largest piles
    return min((piles[0] + piles[1] + piles[2]) // 2, piles[1] + piles[2])
← Back to All Questions