Remove Stones to Minimize the Total
MedPrompt
You are given a 0-indexed integer array piles, where piles[i] represents the number of stones in the ith pile, and an integer k. You should apply the following operation exactly k times:
- Choose any
piles[i]and removeceil(piles[i] / 2)stones from it.
Notice that you can apply the operation on the same pile more than once.
Return the minimum possible total number of stones remaining after applying the k operations.
ceil(x) is the smallest integer that is greater than or equal to x (i.e., rounds x up).
Example 1:
Input: piles = [5,4,9], k = 2
Output: 12
Explanation: Steps of a possible scenario are:
- Apply the operation on pile 2. The resulting piles are [5,4,5].
- Apply the operation on pile 0. The resulting piles are [3,4,5].
The total number of stones in [3,4,5] is 12.Example 2:
Input: piles = [4,3,6,7], k = 3
Output: 12
Explanation: Steps of a possible scenario are:
- Apply the operation on pile 2. The resulting piles are [4,3,3,7].
- Apply the operation on pile 3. The resulting piles are [4,3,3,4].
- Apply the operation on pile 0. The resulting piles are [2,3,3,4].
The total number of stones in [2,3,3,4] is 12.
Constraints:
1 <= piles.length <= 1051 <= piles[i] <= 1041 <= k <= 105
Approaches
3 approaches with complexity analysis and trade-offs.
This approach follows the greedy strategy in the most straightforward way. The core idea is that to minimize the total sum, we should maximize the number of stones removed at each step. The number of stones removed, floor(piles[i] / 2), is maximized when piles[i] is maximized. Therefore, in each of the k steps, we should find the largest pile and apply the operation to it. This method simulates the process directly by repeatedly scanning the array to find the maximum element.
Algorithm
- Loop
ktimes to perform the operations. - In each iteration, find the pile with the maximum number of stones by performing a linear scan through the
pilesarray. - Once the largest pile is found, apply the operation: calculate the number of stones to remove, which is
floor(piles[max_index] / 2), and update the pile's value. - After the loop finishes, iterate through the modified
pilesarray one last time to sum up the remaining stones.
Walkthrough
The algorithm iterates k times. In each iteration, it traverses the entire piles array to locate the pile with the most stones. This search takes O(N) time, where N is the number of piles. After finding the maximum pile, it reduces its size by floor(pile / 2). This process is repeated k times. Finally, the sum of all stones in the piles is calculated and returned.
class Solution { public int minStoneSum(int[] piles, int k) { for (int i = 0; i < k; i++) { // Find the index of the largest pile int maxIndex = 0; for (int j = 1; j < piles.length; j++) { if (piles[j] > piles[maxIndex]) { maxIndex = j; } } // If all piles are empty, we can stop if (piles[maxIndex] == 0) { break; } // Apply the operation: remove floor(piles[maxIndex] / 2) stones int stonesToRemove = piles[maxIndex] / 2; piles[maxIndex] -= stonesToRemove; } // Calculate the total sum int totalStones = 0; for (int pile : piles) { totalStones += pile; } return totalStones; }}Complexity
Time
O(k * N), where N is the number of piles and k is the number of operations. For each of the k operations, we iterate through the entire array of N piles to find the largest one, which takes O(N) time. This leads to a total time complexity of O(k * N).
Space
O(1), as we modify the input array in-place and use only a few extra variables for tracking.
Trade-offs
Pros
Very simple to conceptualize and implement.
Low memory usage as it operates in-place.
Cons
Highly inefficient for large inputs due to the repeated linear scans.
Will likely result in a 'Time Limit Exceeded' (TLE) error on platforms with typical time constraints.
This approach improves upon the brute-force method by optimizing the process of finding the maximum pile. The bottleneck in the previous approach is the O(N) scan to find the maximum in each of the k iterations. A max-heap is a data structure specifically designed for efficiently retrieving the maximum element. By using a max-heap to store the pile sizes, we can find and update the largest pile in logarithmic time instead of linear time, leading to a much faster overall solution.
Algorithm
- Create a max-heap (in Java, a
PriorityQueuewith a reverse order comparator). - Insert all elements from the
pilesarray into the max-heap. This takes O(N) time. - Loop
ktimes:- Extract the maximum element from the heap (O(log N)). This gives us the largest pile.
- Apply the operation to this value:
new_value = old_value - floor(old_value / 2). - Insert the new value back into the heap (O(log N)).
- After the loop, the heap contains the final pile sizes. Sum up all elements in the heap to get the result.
Walkthrough
We first initialize a max-heap and populate it with all the stone counts from the input piles array. Then, we loop k times. In each step, we use the heap's poll() operation to get the largest pile, which takes O(log N) time. We calculate the new size of this pile after removing stones and then add() the new pile size back into the heap, which also takes O(log N) time. After k operations, we sum up the remaining elements in the heap to get the minimum total.
import java.util.PriorityQueue;import java.util.Collections; class Solution { public int minStoneSum(int[] piles, int k) { // Create a max-heap (PriorityQueue with a reverse order comparator) PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder()); // Add all piles to the heap for (int pile : piles) { maxHeap.add(pile); } // Perform k operations for (int i = 0; i < k; i++) { // Get the largest pile int currentPile = maxHeap.poll(); // If largest pile is 0, no more stones can be removed if (currentPile == 0) break; // Calculate stones to remove and the new pile size int stonesToRemove = currentPile / 2; // floor division int newPileSize = currentPile - stonesToRemove; // Add the updated pile back to the heap maxHeap.add(newPileSize); } // Calculate the total sum of remaining stones int totalStones = 0; for (int pile : maxHeap) { totalStones += pile; } return totalStones; }}Complexity
Time
O(N + k * log N), where N is the number of piles and k is the number of operations. Building the initial max-heap takes O(N) time. Each of the k operations involves extracting the maximum (O(log N)) and inserting an element (O(log N)). Thus, the k operations take O(k * log N).
Space
O(N), as the max-heap needs to store all N pile sizes.
Trade-offs
Pros
Significantly more efficient than the brute-force approach.
Correctly implements the optimal greedy strategy.
Passes within typical time limits for the given constraints.
Cons
Requires extra space proportional to the number of piles to store the heap.
This is the most efficient approach for the given constraints. It leverages the fact that the maximum number of stones in a pile is relatively small (10^4). Instead of storing each pile individually in a data structure like a heap, we can group piles of the same size together. A frequency array (or a hash map) is used for this purpose. This avoids the logarithmic time complexity of heap operations and replaces them with constant-time array lookups and updates, making the process of finding and updating the largest pile very fast.
Algorithm
- Given that pile sizes are limited (up to 10^4), create a frequency array,
freq, of size 10001.freq[i]will store the count of piles withistones. - Populate the
freqarray by iterating through the inputpiles. Keep track of the maximum pile size encountered. - Loop
ktimes:- Start from the current maximum pile size and scan downwards to find the largest size
sfor whichfreq[s] > 0. - Decrement
freq[s](one pile of this size is used). - Calculate the new pile size:
new_s = s - floor(s / 2). - Increment
freq[new_s].
- Start from the current maximum pile size and scan downwards to find the largest size
- After
koperations, calculate the total sum by iterating through the frequency array:sum += i * freq[i]for alli.
Walkthrough
We use an array freq of size 10001 as a frequency map, where freq[i] stores how many piles have i stones. We also maintain a pointer, maxPileSize, to the largest pile size currently available. In each of the k iterations, we find the largest pile by starting from maxPileSize and moving downwards until we find a non-empty bucket. We then perform the operation by decrementing the count of the large pile and incrementing the count of the new, smaller pile. This is faster than a heap because finding the max involves a simple scan (which is amortized efficient) and updates are O(1). The total time is dominated by the initial population of the array and the k operations.
class Solution { public int minStoneSum(int[] piles, int k) { // Max pile size is 10^4, so array size 10001 int[] freq = new int[10001]; int maxPileSize = 0; // Populate frequency array and find initial max pile size for (int pile : piles) { freq[pile]++; maxPileSize = Math.max(maxPileSize, pile); } // Perform k operations for (int i = 0; i < k; i++) { // Find the largest pile size available while (maxPileSize > 0 && freq[maxPileSize] == 0) { maxPileSize--; } // If no piles are left to operate on if (maxPileSize == 0) { break; } // Take one pile of the largest size freq[maxPileSize]--; // Calculate the new pile size int newPileSize = maxPileSize - (maxPileSize / 2); // Add the new pile to the frequency count freq[newPileSize]++; } // Calculate the total sum int totalStones = 0; for (int i = 1; i <= 10000; i++) { if (freq[i] > 0) { totalStones += i * freq[i]; } } return totalStones; }}Complexity
Time
O(N + k + M), where N is the number of piles, k is the number of operations, and M is the maximum possible value of a pile. Populating the frequency array takes O(N). The main loop runs k times. The total work for finding the maximum across all k iterations is bounded by O(k + M) because the `maxPileSize` pointer only moves downwards. The final summation takes O(M).
Space
O(M), where M is the maximum possible pile size (10001 in this problem). We need an array to store the frequency of each pile size.
Trade-offs
Pros
The most efficient approach for the given constraints.
Faster than the heap-based approach due to constant-time updates and better cache performance.
Can be more space-efficient than the heap if the number of piles N is larger than the maximum pile size M.
Cons
The space complexity depends on the maximum possible value of a pile, not the number of elements. This could be a drawback if pile sizes were much larger.
Solutions
Solution
class Solution {public int minStoneSum(int[] piles, int k) { PriorityQueue<Integer> pq = new PriorityQueue<>((a, b)->b - a); for (int x : piles) { pq.offer(x); } while (k-- > 0) { int x = pq.poll(); pq.offer(x - x / 2); } int ans = 0; while (!pq.isEmpty()) { ans += pq.poll(); } return ans; }}class Solution {public: int minStoneSum(vector<int> &piles, int k) { priority_queue<int> pq; for (int x : piles) { pq.push(x); } while (k--) { int x = pq.top(); pq.pop(); pq.push(x - x / 2); } int ans = 0; while (!pq.empty()) { ans += pq.top(); pq.pop(); } return ans; }};class Solution: def minStoneSum(self, piles: List[int], k: int) -> int: pq = [- x for x in piles] heapify(pq) for _ in range(k): heapreplace(pq, pq[0] // 2) return - sum(pq)Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.