1753. Maximum Score From Removing Stones

Problem Description

You are tasked with a solitaire game involving three piles of stones. The sizes of the piles are given by three integers a, b, and c. The game is played by removing one stone from two different non-empty piles at a time, which adds one point to your score. This process continues until you are left with fewer than two non-empty piles, which means there are no more moves to make. The objective is to determine the maximum score possible by the end of the game.

Intuition

The solution approach involves some straightforward observations.

Whenever you take a stone from two piles, you want to reduce the difference between the number of stones in the piles to maximize the number of moves you can make. This is because removing stones from just the two largest piles when another pile is empty will end the game prematurely.
If the sum of the stones in the two smaller piles is less than the number of stones in the largest pile (a + b < c), then you will eventually have to pick from the largest pile (c) until it equals the sum of the other two piles. You cannot score more points than the total stones available in the two smallest piles.
Otherwise, if a + b >= c, you can keep taking stones from the two piles with the most stones until all piles have the same number of stones. Then, you simply alternate between pairs of piles, making each of them empty around the same time, ending the game with only one stone left in one pile or none.

Consequently, the maximum score is the sum of the stones in all piles divided by two, using integer division, since each move decreases the total number of stones by two ((a + b + c) >> 1). Integer division is important because if there's an odd number of total stones, one will remain at the end unpaired, and thus, not contributing to the score.

The solution uses a bitwise right shift >> by 1 to perform integer division by 2 on the sum of the stone counts, which is a common practice in programming for efficiency.

Learn more about Greedy, Math and Heap (Priority Queue) patterns.

Solution Approach

The implementation of the solution is direct and doesn't require complicated algorithms or data structures. It's an arithmetic problem that is solved using basic mathematical operations and sorting. Here's a step-by-step walkthrough of the implementation:

Sorting the Inputs: The first step is to sort the integers a, b, and c. Since the problem doesn't require you to work with the original piles but just their sizes, sorting simplifies the logic by always ensuring that a <= b <= c (a, being the smallest, and c the largest after sorting).
Handling the Edge Case: We then check if the sum of the smaller two piles (a + b) is less than the size of the largest pile (c). If this condition is true, this means that you can continue to take stones from the two smaller piles until one or both of them are empty, and you can score no more than a + b points. Therefore, if a + b < c, we simply return a + b.
Calculating Maximum Score Otherwise: If the previous condition isn't met (i.e., a + b >= c), it indicates that you can balance the stones between the three piles while making moves. In this case, the maximum score you can get is half of the total number of stones, since each move reduces the total stone count by 2. This is calculated using the expression (a + b + c) >> 1 which is equivalent to dividing the sum by two, but it is computed more efficiently through bitwise shifting.

No complex data structures are needed because we track only the sizes of the piles, not the individual stones. The problem doesn't require keeping track of the moves or the configuration of the piles after each move. As such, the algorithm is a clear instance of greedy strategy, where we make a local optimal choice (balancing the piles while we make moves) that leads to a global optimum (maximum score).

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's illustrate the solution approach with a small example. Consider three piles of stones with sizes a = 2, b = 4, and c = 6.

Following the steps outlined in the solution approach:

Sorting the Inputs: We sort the numbers so that a <= b <= c. In this case, a = 2, b = 4, and c = 6, which are already sorted.
Handling the Edge Case: We check if a + b < c. Here, a + b = 2 + 4 = 6, which is equal to c. Since it's not smaller than c, we don't return a + b as the score.
Calculating Maximum Score Otherwise: Since a + b >= c, we proceed to calculate the maximum score as the sum of all the stones divided by two. The total number of stones is a + b + c = 2 + 4 + 6 = 12. We then perform integer division by two, which can be done efficiently with a bitwise right shift: (12 >> 1) = 6.

Thus, the maximum score possible with these three piles is 6. This means we can make 6 moves wherein each time, we remove one stone from two different piles until we can't make any more moves.

To visualize it, the sequence of moves could be:

Move 1: Remove one stone from piles b and c (a = 2, b = 3, c = 5), score = 1.
Move 2: Remove one stone from piles b and c (a = 2, b = 2, c = 4), score = 2.
Move 3: Remove one stone from piles a and c (a = 1, b = 2, c = 3), score = 3.
Move 4: Remove one stone from piles a and b (a = 0, b = 1, c = 3), score = 4. (Now a is empty)
Move 5: Remove one stone from piles b and c (a = 0, b = 0, c = 2), score = 5. (Now b is also empty)
Move 6: We cannot make any more moves as two piles are empty.

The games end with a maximum score of 6, in alignment with our calculated maximum score.

Solution Implementation

1class Solution:
2    def maximumScore(self, num1: int, num2: int, num3: int) -> int:
3        # Sort the input numbers to ensure num1 <= num2 <= num3
4        num1, num2, num3 = sorted([num1, num2, num3])
5
6        # If the sum of the two smallest numbers is less than the largest,
7        # the maximum score is the sum of the smaller two.
8        # This is because we can only take one stone each time,
9        # and we should pair each stone from a smaller pile with one from
10        # the largest pile until the smaller piles are empty.
11        if num1 + num2 <= num3:
12            return num1 + num2
13      
14        # Otherwise, the maximum score is half of the total number of stones,
15        # rounded down, because we take one stone from two different piles
16        # until it's not possible anymore.
17        return (num1 + num2 + num3) // 2
18        # Note: The right shift operator (>>) was replaced with floor division (//)
19        # for better readability, as it's more commonly used to represent integer division.
20

1class Solution {
2    public int maximumScore(int a, int b, int c) {
3        // Create an array to hold the input values
4        int[] sides = new int[] {a, b, c};
5      
6        // Sort the array in ascending order
7        Arrays.sort(sides);
8      
9        // Check if the sum of the two smaller numbers is smaller than the largest number
10        if (sides[0] + sides[1] < sides[2]) {
11            // The maximum score is the sum of the two smaller numbers
12            return sides[0] + sides[1];
13        }
14      
15        // Otherwise, the maximum score is half the sum of all three numbers
16        // Using bitwise shift to the right to divide by 2
17        return (a + b + c) >> 1;
18    }
19}
20

1#include <vector> // Include the vector header for using std::vector
2#include <algorithm> // Include the algorithm header for using std::sort
3
4class Solution {
5public:
6    // Function to calculate the maximum score by choosing stones from three piles
7    int maximumScore(int a, int b, int c) {
8        // Create a vector to store the values of the three piles
9        std::vector<int> piles = {a, b, c};
10      
11        // Sort the vector in non-decreasing order
12        std::sort(piles.begin(), piles.end());
13      
14        // After sorting, piles[0] is the smallest, and piles[2] is the largest.
15        // If the sum of the two smaller piles is less than the largest pile,
16        // the maximum score is the sum of those two smaller piles.
17        if (piles[0] + piles[1] < piles[2]) {
18            return piles[0] + piles[1];
19        } else {
20            // Otherwise, the maximum score is half the sum of all piles,
21            // because we will eventually be taking stones from two piles,
22            // one by one, until one or both of the two smaller piles is empty. 
23            return (a + b + c) / 2; // Using integer division for the right shift equivalent
24        }
25    }
26};
27

1// Function to calculate the maximum score by choosing stones from three piles
2function maximumScore(a: number, b: number, c: number): number {
3  // Create an array to store the values of the three piles
4  const piles: number[] = [a, b, c];
5
6  // Sort the array in non-decreasing order
7  piles.sort((x, y) => x - y);
8
9  // After sorting, piles[0] is the smallest, and piles[2] is the largest.
10  // If the sum of the two smaller piles is less than the largest pile,
11  // The maximum score is the sum of those two smaller piles.
12  if (piles[0] + piles[1] < piles[2]) {
13    return piles[0] + piles[1];
14  } else {
15    // Otherwise, the maximum score is half the sum of all piles,
16    // because we will eventually be taking stones from two piles,
17    // one by one, until one or both of the two smaller piles is empty.
18    // Using Math.floor for integer division to get the equivalent result as right shifting in other languages like C++.
19    return Math.floor((a + b + c) / 2);
20  }
21}
22
23// Example usage:
24// const score = maximumScore(2, 4, 6);
25// console.log(`The maximum score is: ${score}`);
26

Time and Space Complexity

Time Complexity

The time complexity of the code is determined by the sorting operation and the subsequent conditional checks. The sorting of three numbers has a constant time complexity, O(1), since there are a finite number of permutations for three elements regardless of their values.

After sorting, we perform a conditional check and return a value based on the comparison. These operations are also done in constant time O(1) since we're just using arithmetic operations which take a fixed amount of time.

Therefore, the total time complexity of the code is O(1).

Space Complexity

The space complexity of the code is also O(1) because the space required does not depend on the size of the input. All we're doing is assigning sorted values to the variables a, b, c, and doing a few arithmetic operations which do not require additional space that depends on the input size. The additional space used is constant.

So, the space complexity is O(1).

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

What's the output of running the following function using input 56?

1KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12def letter_combinations_of_phone_number(digits):
13    def dfs(path, res):
14        if len(path) == len(digits):
15            res.append(''.join(path))
16            return
17
18        next_number = digits[len(path)]
19        for letter in KEYBOARD[next_number]:
20            path.append(letter)
21            dfs(path, res)
22            path.pop()
23
24    res = []
25    dfs([], res)
26    return res
27

1private static final Map<Character, char[]> KEYBOARD = Map.of(
2    '2', "abc".toCharArray(),
3    '3', "def".toCharArray(),
4    '4', "ghi".toCharArray(),
5    '5', "jkl".toCharArray(),
6    '6', "mno".toCharArray(),
7    '7', "pqrs".toCharArray(),
8    '8', "tuv".toCharArray(),
9    '9', "wxyz".toCharArray()
10);
11
12public static List<String> letterCombinationsOfPhoneNumber(String digits) {
13    List<String> res = new ArrayList<>();
14    dfs(new StringBuilder(), res, digits.toCharArray());
15    return res;
16}
17
18private static void dfs(StringBuilder path, List<String> res, char[] digits) {
19    if (path.length() == digits.length) {
20        res.add(path.toString());
21        return;
22    }
23    char next_digit = digits[path.length()];
24    for (char letter : KEYBOARD.get(next_digit)) {
25        path.append(letter);
26        dfs(path, res, digits);
27        path.deleteCharAt(path.length() - 1);
28    }
29}
30

1const KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12function letter_combinations_of_phone_number(digits) {
13    let res = [];
14    dfs(digits, [], res);
15    return res;
16}
17
18function dfs(digits, path, res) {
19    if (path.length === digits.length) {
20        res.push(path.join(''));
21        return;
22    }
23    let next_number = digits.charAt(path.length);
24    for (let letter of KEYBOARD[next_number]) {
25        path.push(letter);
26        dfs(digits, path, res);
27        path.pop();
28    }
29}
30

["jk", "mno"]

["jm", "kn", "lo"]

["jklmnp"]

["jm","jn","jo","km","kn","ko","lm","ln","lo"]

I don’t know