# Remove Stones to Minimize the Total
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/remove-stones-to-minimize-the-total)
Canonical: https://scaleengineer.com/dsa/problems/remove-stones-to-minimize-the-total
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Data structures:** Array, Heap (Priority Queue)
---
## Problem
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** `ceil(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 <= 105`
* `1 <= piles[i] <= 104`
* `1 <= k <= 105`

# Approaches
## Brute Force Simulation by Repeatedly Finding the Maximum
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.
**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.
**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.
### Explanation
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.

```java
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;
    }
}
```
### Algorithm
- Loop `k` times to perform the operations.
- In each iteration, find the pile with the maximum number of stones by performing a linear scan through the `piles` array.
- 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 `piles` array one last time to sum up the remaining stones.

## Greedy Approach with a Max-Heap (Priority Queue)
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.
**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.
**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.
### Explanation
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.

```java
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;
    }
}
```
### Algorithm
- Create a max-heap (in Java, a `PriorityQueue` with a reverse order comparator).
- Insert all elements from the `piles` array into the max-heap. This takes O(N) time.
- Loop `k` times:
  - 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.

## Optimized Greedy Approach using a Frequency Array
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.
**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.
**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.
### Explanation
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.

```java
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;
    }
}
```
### 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 with `i` stones.
- Populate the `freq` array by iterating through the input `piles`. Keep track of the maximum pile size encountered.
- Loop `k` times:
  - Start from the current maximum pile size and scan downwards to find the largest size `s` for which `freq[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]`.
- After `k` operations, calculate the total sum by iterating through the frequency array: `sum += i * freq[i]` for all `i`.

# Solutions
### Java

```java
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;
  }
}

```

### CPP

```cpp
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;
  }
};

```

### Python

```python
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)

```