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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Maximum Score From Removing Stones

Number: 1879

Difficulty: Medium

Paid? No

Companies: Google

Problem Description

Given three piles of stones with counts a, b, and c, you can remove one stone from any two distinct non-empty piles per move, earning 1 point per move. The game terminates when fewer than two piles have stones. The goal is to compute the maximum achievable score.

Key Insights

  • Every move removes exactly two stones, so without restrictions, the total possible moves would be (a + b + c) / 2.
  • The game is limited by the situation where one pile has significantly more stones than the sum of the other two; moves can only be made until the two smaller piles are exhausted.
  • Therefore, the maximum score is the minimum of the total stones divided by 2, and the sum of the two smallest piles (or, equivalently, the total stones minus the largest pile).

Space and Time Complexity

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

Solution

The key observation is that each move uses two stones, so the maximum possible number of moves is (a + b + c) / 2 if all stones could be paired perfectly. However, if one pile is too large (i.e., larger than the sum of the other two piles), then the extra stones in that pile cannot form a pair once the other two are exhausted. Thus, the answer is the smaller value between (a + b + c) / 2 and (a + b + c) minus the largest pile. This solution uses basic arithmetic operations and is achieved in constant time and space.

Code Solutions

def maximumScore(a: int, b: int, c: int) -> int:
    # Calculate the total number of stones
    total = a + b + c
    # Find the largest pile among a, b, and c
    max_pile = max(a, b, c)
    # The maximum score is the smaller value between total//2 and total - max_pile
    return min(total // 2, total - max_pile)

# Example usage:
# print(maximumScore(2, 4, 6)) should return 6
← Back to All Questions