Remove Stones to Minimize the Total
Remove Stones to Minimize the Total is a medium heaps problem solved with the top k / kth largest / smallest pattern.
The best approach, optimal (greedy with a max-heap), runs in O(n + k log n) time and O(n) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (scan for the largest pile each time) up.
Problem
You are given an array piles, where piles[i] is the number of stones in pile i, and an integer k. One operation picks any pile and throws away floor(piles[i] / 2) of its stones. The same pile may be picked more than once.
Apply exactly k operations and return the smallest possible total number of stones left across all piles.
Examples
Example 1
- Input
piles = [9, 4, 6], k = 2- Output
12- Why
- Halve the 9 pile (remove 4, leaving 5): [5, 4, 6]. Then halve the 6 pile (remove 3): [5, 4, 3]. Total 12.
Example 2
- Input
piles = [10, 3, 7, 2], k = 3- Output
12- Why
- 10 -> 5 removes 5, then 7 -> 4 removes 3, then the largest pile is 5 and 5 -> 3 removes 2. The piles end as [3, 3, 4, 2], total 12.
Constraints
1 <= piles.length <= 10^51 <= piles[i] <= 10^41 <= k <= 10^5
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (2 examples, or your own). Submit also runs 12 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (scan for the largest pile each time) | O(n · k) | O(n) |
| Optimal (greedy with a max-heap) | O(n + k log n) | O(n) |
1Brute force (scan for the largest pile each time)
O(n · k)Each of the k operations scans all n piles.O(n)A working copy of the piles.Repeat k times: find the largest pile with a linear scan and remove half of it (rounded down). Sum the piles at the end.
- Copy piles into an array.
- k times: find index m of the maximum; piles[m] -= piles[m] / 2.
- Return the sum of all piles.
class Solution {
public int minStoneSum(int[] piles, int k) {
int[] p = piles.clone();
for (int op = 0; op < k; op++) {
int m = 0;
for (int i = 1; i < p.length; i++) {
if (p[i] > p[m]) m = i;
}
p[m] -= p[m] / 2;
}
int total = 0;
for (int x : p) total += x;
return total;
}
}class Solution:
def minStoneSum(self, piles: List[int], k: int) -> int:
p = list(piles)
for _ in range(k):
m = 0
for i in range(1, len(p)):
if p[i] > p[m]:
m = i
p[m] -= p[m] // 2
return sum(p)class Solution {
public:
int minStoneSum(vector<int>& piles, int k) {
vector<int> p = piles;
int n = p.size();
for (int op = 0; op < k; op++) {
int m = 0;
for (int i = 1; i < n; i++) {
if (p[i] > p[m]) m = i;
}
p[m] -= p[m] / 2;
}
int total = 0;
for (int x : p) total += x;
return total;
}
};function minStoneSum(piles, k) {
const p = piles.slice();
for (let op = 0; op < k; op++) {
let m = 0;
for (let i = 1; i < p.length; i++) {
if (p[i] > p[m]) m = i;
}
p[m] -= Math.floor(p[m] / 2);
}
let total = 0;
for (const x of p) total += x;
return total;
}2Optimal (greedy with a max-heap)
O(n + k log n)Building the heap is O(n log n) at most, and each of the k operations is one pop and one push.O(n)The heap holds all n piles.Put every pile into a max-heap. k times, pop the largest pile x, subtract floor(x / 2) from the running total, and push back x - floor(x / 2). Stopping early is safe once the largest pile is 1, since no further operation removes anything.
- total = sum of piles; push every pile into a max-heap.
- Repeat k times: x = pop; if x == 1, stop; total -= x / 2; push x - x / 2.
- Return total.
class Solution {
public int minStoneSum(int[] piles, int k) {
PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
int total = 0;
for (int x : piles) {
pq.offer(x);
total += x;
}
for (int op = 0; op < k; op++) {
int x = pq.poll();
if (x == 1) break;
total -= x / 2;
pq.offer(x - x / 2);
}
return total;
}
}class Solution:
def minStoneSum(self, piles: List[int], k: int) -> int:
heap = [-x for x in piles]
heapq.heapify(heap)
total = sum(piles)
for _ in range(k):
x = -heapq.heappop(heap)
if x == 1:
break
total -= x // 2
heapq.heappush(heap, -(x - x // 2))
return totalclass Solution {
public:
int minStoneSum(vector<int>& piles, int k) {
priority_queue<int> pq(piles.begin(), piles.end());
int total = 0;
for (int x : piles) total += x;
for (int op = 0; op < k; op++) {
int x = pq.top();
pq.pop();
if (x == 1) break;
total -= x / 2;
pq.push(x - x / 2);
}
return total;
}
};function minStoneSum(piles, k) {
// array-based binary max-heap
const heap = [];
const push = (v) => {
heap.push(v);
let i = heap.length - 1;
while (i > 0) {
const p = (i - 1) >> 1;
if (heap[p] >= heap[i]) break;
[heap[p], heap[i]] = [heap[i], heap[p]];
i = p;
}
};
const pop = () => {
const top = heap[0];
const last = heap.pop();
if (heap.length > 0) {
heap[0] = last;
let i = 0;
while (true) {
const l = 2 * i + 1, r = l + 1;
let m = i;
if (l < heap.length && heap[l] > heap[m]) m = l;
if (r < heap.length && heap[r] > heap[m]) m = r;
if (m === i) break;
[heap[m], heap[i]] = [heap[i], heap[m]];
i = m;
}
}
return top;
};
let total = 0;
for (const x of piles) {
push(x);
total += x;
}
for (let op = 0; op < k; op++) {
const x = pop();
if (x === 1) break;
const half = Math.floor(x / 2);
total -= half;
push(x - half);
}
return total;
}Edge cases to test
- Piles of size 1: halving removes floor(1 / 2) = 0 stones
- k much larger than the number of piles, so the same pile is halved many times
- A single pile
- All piles equal
Hints
Hint 1
Halving a pile of size x removes floor(x / 2) stones, which is largest when x is largest.
Hint 2
Always halving the current largest pile is optimal: an operation never makes any pile bigger, so taking the biggest removal now never blocks a better one later.
Hint 3
A max-heap gives the largest pile in O(log n), and the halved pile goes straight back in.
FAQ
What is the best time complexity for Remove Stones to Minimize the Total?
Optimal (greedy with a max-heap) runs in O(n + k log n) time and O(n) extra space. Building the heap is O(n log n) at most, and each of the k operations is one pop and one push.
Which pattern does Remove Stones to Minimize the Total use?
It is a heaps problem that uses the top k / kth largest / smallest pattern. Other problems with the same pattern: Kth Largest Element in an Array, Kth Largest Element in a Stream, Top K Frequent Words.
Is there a brute force solution for Remove Stones to Minimize the Total?
Yes. Brute force (scan for the largest pile each time) takes O(n · k) time and O(n) space. Repeat k times: find the largest pile with a linear scan and remove half of it (rounded down).
Which edge cases should I test for Remove Stones to Minimize the Total?
Piles of size 1: halving removes floor(1 / 2) = 0 stones; k much larger than the number of piles, so the same pile is halved many times; A single pile; All piles equal.