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.
How many times is a tree node visited in a depth first search?
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, andc. Since the problem doesn't require you to work with the original piles but just their sizes, sorting simplifies the logic by always ensuring thata <= b <= c(a, being the smallest, andcthe 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 thana + bpoints. Therefore, ifa + b < c, we simply returna + 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) >> 1which 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).
Which of these properties could exist for a graph but not a tree?
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, andc = 6, which are already sorted. -
Handling the Edge Case: We check if
a + b < c. Here,a + b = 2 + 4 = 6, which is equal toc. Since it's not smaller thanc, we don't returna + bas 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 isa + 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
bandc(a = 2,b = 3,c = 5), score = 1. - Move 2: Remove one stone from piles
bandc(a = 2,b = 2,c = 4), score = 2. - Move 3: Remove one stone from piles
aandc(a = 1,b = 2,c = 3), score = 3. - Move 4: Remove one stone from piles
aandb(a = 0,b = 1,c = 3), score = 4. (Nowais empty) - Move 5: Remove one stone from piles
bandc(a = 0,b = 0,c = 2), score = 5. (Nowbis 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.
201class 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}
201#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};
271// 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}`);
26What is the space complexity of the following code?
1int sum(int n) {
2 if (n <= 0) {
3 return 0;
4 }
5 return n + sum(n - 1);
6}
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.
Given a sorted array of integers and an integer called target, find the element that
equals to the target and return its index. Select the correct code that fills the
___ in the given code snippet.
1def binary_search(arr, target):
2 left, right = 0, len(arr) - 1
3 while left ___ right:
4 mid = (left + right) // 2
5 if arr[mid] == target:
6 return mid
7 if arr[mid] < target:
8 ___ = mid + 1
9 else:
10 ___ = mid - 1
11 return -1
121public static int binarySearch(int[] arr, int target) {
2 int left = 0;
3 int right = arr.length - 1;
4
5 while (left ___ right) {
6 int mid = left + (right - left) / 2;
7 if (arr[mid] == target) return mid;
8 if (arr[mid] < target) {
9 ___ = mid + 1;
10 } else {
11 ___ = mid - 1;
12 }
13 }
14 return -1;
15}
161function binarySearch(arr, target) {
2 let left = 0;
3 let right = arr.length - 1;
4
5 while (left ___ right) {
6 let mid = left + Math.trunc((right - left) / 2);
7 if (arr[mid] == target) return mid;
8 if (arr[mid] < target) {
9 ___ = mid + 1;
10 } else {
11 ___ = mid - 1;
12 }
13 }
14 return -1;
15}
16Recommended Readings
Greedy Introduction iframe width 560 height 315 src https www youtube com embed WTslqPbj7I title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture web share allowfullscreen iframe When do we use greedy Greedy algorithms tend to solve optimization problems Typically they will ask you
Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you
https algomonster s3 us east 2 amazonaws com cover_photos heap svg Priority Queue and Heap What is the relationship between priority queue and heap Priority Queue is an Abstract Data Type and Heap is the concrete data structure we use to implement a priority queue Priority Queue A priority queue
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.