{x}
blog image

Remove Stones to Minimize the Total

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 remove floor(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.

floor(x) is the greatest integer that is smaller than or equal to x (i.e., rounds x down).

 

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 <= 105
  • 1 <= piles[i] <= 104
  • 1 <= k <= 105

Solution Explanation: Remove Stones to Minimize the Total

This problem asks us to find the minimum total number of stones remaining after applying a specific operation k times. The operation involves selecting a pile of stones and removing floor(piles[i] / 2) stones. The optimal strategy is to greedily remove stones from the largest piles.

Approach: Greedy with Max Heap

The solution uses a greedy approach combined with a max-heap (priority queue) data structure. The steps are:

  1. Create a Max Heap: We create a max-heap to store the pile sizes. A max-heap ensures that we always have access to the largest pile.

  2. Iterate k times: We iterate k times, performing the following steps in each iteration:

    • Extract Max: Remove the largest pile size from the heap.
    • Apply Operation: Calculate the number of stones to remove (x - x/2), where x is the largest pile size.
    • Insert Back: Insert the reduced pile size back into the heap.

  3. Calculate Total: After k iterations, the sum of all elements remaining in the heap represents the minimum total number of stones.

Time and Space Complexity

  • Time Complexity: O(k log n), where n is the number of piles and k is the number of operations. Building the heap takes O(n log n) in the worst case, but that's dominated by the k iterations, each of which involves a heap operation (O(log n)).
  • Space Complexity: O(n) to store the heap.

Code Examples

The code examples below demonstrate the solution in different programming languages. They all follow the same core algorithm described above.

Python:

import heapq
 
class Solution:
    def minStoneSum(self, piles: List[int], k: int) -> int:
        # Create a max-heap (negate values for max-heap behavior)
        heap = [-x for x in piles]
        heapq.heapify(heap)
 
        for _ in range(k):
            # Extract the largest pile
            largest_pile = heapq.heappop(heap)
            # Apply the operation and add back to the heap
            heapq.heappush(heap, largest_pile // 2)
 
        # Return the sum of remaining stones (negate to get positive sum)
        return -sum(heap)

Java:

import java.util.PriorityQueue;
import java.util.Collections;
 
class Solution {
    public int minStoneSum(int[] piles, int k) {
        // Create a max-heap priority queue
        PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
        for (int pile : piles) {
            pq.offer(pile);
        }
 
        for (int i = 0; i < k; i++) {
            int largest = pq.poll();
            pq.offer(largest - largest / 2);
        }
 
        int total = 0;
        for (int pile : pq) {
            total += pile;
        }
        return total;
    }
}

C++:

#include <queue>
#include <vector>
#include <algorithm>
 
using namespace std;
 
class Solution {
public:
    int minStoneSum(vector<int>& piles, int k) {
        // Create a max-heap priority queue
        priority_queue<int> pq;
        for (int pile : piles) {
            pq.push(pile);
        }
 
        for (int i = 0; i < k; i++) {
            int largest = pq.top();
            pq.pop();
            pq.push(largest - largest / 2);
        }
 
        int total = 0;
        while (!pq.empty()) {
            total += pq.top();
            pq.pop();
        }
        return total;
    }
};

Go:

import (
	"container/heap"
	"sort"
)
 
type hp struct{ sort.IntSlice }
 
func (h hp) Less(i, j int) bool { return h.IntSlice[i] > h.IntSlice[j] }
func (h *hp) Push(v interface{}) { h.IntSlice = append(h.IntSlice, v.(int)) }
func (h *hp) Pop() interface{} {
	a := h.IntSlice
	v := a[len(a)-1]
	h.IntSlice = a[:len(a)-1]
	return v
}
 
func minStoneSum(piles []int, k int) int {
	pq := &hp{piles}
	heap.Init(pq)
 
	for i := 0; i < k; i++ {
		largest := heap.Pop(pq).(int)
		heap.Push(pq, largest-largest/2)
	}
 
	sum := 0
	for pq.Len() > 0 {
		sum += heap.Pop(pq).(int)
	}
	return sum
}

These examples all implement the same core greedy algorithm using a priority queue for efficiency. Remember to adapt the code to your specific environment and coding style.