Remove Stones to Minimize the Total — Problem & Solution
Remove Stones to Minimize the Total solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Remove Stones to Minimize the Total is a medium coding problem on arrays, greedy and heap, asked in Amazon and Google interviews.
- Difficulty: Medium
- Topics: Arrays, Greedy, Heap
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given piles, where piles[i] is the number of stones in the i-th pile, and an integer k.
You must perform exactly k operations. In one operation you pick any pile — call its size x — and remove floor(x / 2) stones from it, leaving x - floor(x / 2). The same pile may be picked any number of times.
Return the smallest total number of stones that can remain across all piles after the k operations.
Example 1
Input: piles = [6,3,10], k = 3
Output: 9
Explanation: Halve 10 to 5, then 6 to 3, then 5 to 3: the piles end as [3,3,3].
Example 2
Input: piles = [4,3,6,7], k = 3
Output: 12
Explanation: 7 becomes 4, 6 becomes 3, one of the 4s becomes 2: [2,3,3,4].
Example 3
Input: piles = [1], k = 5
Output: 1
Explanation: A pile of one stone loses `floor(1 / 2) = 0` stones each time.
Constraints
1 <= piles.length <= 10^51 <= piles[i] <= 10^41 <= k <= 10^5
Hints for Remove Stones to Minimize the Total
Hint 1
An operation on a pile of size
xremovesfloor(x / 2)stones — the bigger the pile, the bigger the saving.Hint 2
Every operation is independent of the order the others happen in, so greedily take the largest saving available right now.
Hint 3
Keep the piles in a max-heap: pop the largest, push back
x - floor(x / 2),ktimes, then add up what is left.
How to solve Remove Stones to Minimize the Total
Each operation should hit the currently largest pile, because that pile yields the largest removal and halving a pile never makes it larger than any pile you skipped. A max-heap serves the largest pile in O(log n).
Approach
- Put every pile size into a max-heap.
- Repeat
ktimes: pop the largest sizexand pushx - floor(x / 2)back. - Return the sum of the sizes left in the heap.
Why it works
Suppose an optimal plan spends some operation on a pile smaller than the current maximum M. Swapping that operation onto M removes floor(M / 2) instead of something no larger, and every later operation still has a pile at least as large to work on, so the total never gets worse. Repeating the exchange turns any optimal plan into the greedy one.
Complexity
- Time —
O((n + k) log n) - Space —
O(n)
Pitfalls
- The amount removed is
floor(x / 2), so a pile keeps the ceiling: 5 becomes 3, not 2. - All
koperations are mandatory, but once the largest pile is 1 they remove nothing — the loop still terminates correctly. - Sorting once is not enough: a halved pile can still be the largest and must compete again.
Reference solution
Python
from typing import List
import heapq
def minStoneSum(piles: List[int], k: int) -> int:
heap = [-p for p in piles] # max-heap through negation
heapq.heapify(heap)
for _ in range(k):
top = -heapq.heappop(heap)
heapq.heappush(heap, -(top - top // 2))
return -sum(heap)Java
public static int minStoneSum(int[] piles, int k) {
PriorityQueue<Integer> heap = new PriorityQueue<>(Collections.reverseOrder());
for (int p : piles) heap.add(p);
for (int t = 0; t < k; t++) {
int top = heap.poll();
heap.add(top - top / 2);
}
int total = 0;
for (int p : heap) total += p;
return total;
}C++
int minStoneSum(vector<int>& piles, int k) {
priority_queue<int> heap(piles.begin(), piles.end());
for (int t = 0; t < k; t++) {
int top = heap.top();
heap.pop();
heap.push(top - top / 2);
}
int total = 0;
while (!heap.empty()) {
total += heap.top();
heap.pop();
}
return total;
}JavaScript
var minStoneSum = function(piles, k) {
// A max-heap kept as a min-heap of negated sizes.
var heap = [];
for (var i = 0; i < piles.length; i++) heapPush(heap, -piles[i]);
for (var t = 0; t < k; t++) {
var top = -heapPop(heap);
heapPush(heap, -(top - Math.floor(top / 2)));
}
var total = 0;
for (var j = 0; j < heap.length; j++) total -= heap[j];
return total;
};
var heapPush = function(h, v) {
h.push(v);
var i = h.length - 1;
while (i > 0) {
var p = (i - 1) >> 1;
if (h[p] <= h[i]) break;
var t = h[p]; h[p] = h[i]; h[i] = t;
i = p;
}
};
var heapPop = function(h) {
var top = h[0];
var last = h.pop();
if (h.length > 0) {
h[0] = last;
var j = 0;
for (;;) {
var l = 2 * j + 1, r = l + 1, s = j;
if (l < h.length && h[l] < h[s]) s = l;
if (r < h.length && h[r] < h[s]) s = r;
if (s === j) break;
var t = h[s]; h[s] = h[j]; h[j] = t;
j = s;
}
}
return top;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Greedy Algorithms