1962. Remove Stones to Minimize the Total
Asked at Salesforce
Difficulty
Medium
Time
O(n + k log n)
Space
O(n)
Pattern
Array
Companies
1
Problem
You get an array piles, where piles[i] is the number of stones in pile i, and an integer k. You must apply this operation exactly k times: pick any pile and remove floor(piles[i] / 2) stones from it. floor means round down, so a pile of 5 loses 2 stones and a pile of 1 loses 0.
You may use the same pile more than once. Your goal is to make the total number of stones left as small as possible, and you return that minimum total.
Because you always want to cut the biggest pile, the greedy choice is to apply each operation to the pile with the most stones at that moment. A max-heap (a priority queue that always gives you the largest value) lets you find and update that pile quickly.
Each cut removes half of one pile
Constraints
- ●
1 <= piles.length <= 10^5 - ●
1 <= piles[i] <= 10^4 - ●
1 <= k <= 10^5
Examples
piles = [5,4,9], k = 212piles = [4,3,6,7], k = 312Asked At
1 companies| Company | Difficulty | |
|---|---|---|
| Salesforce | Medium | View all Salesforce questions → |
How to Think About It
Greedy intuition: always remove from the largest pile to minimize the total fastest. A max-heap lets you efficiently find and update the largest pile in O(log n) time.
Why max-heap: you always want to reduce the largest pile. A max-heap gives O(1) access to the max and O(log n) for insert/pop. After each operation, push the reduced pile back into the heap.
The algorithm: build a max-heap from piles. Repeat k times: pop the max, divide by 2 (floor), push the result back. After k operations, sum the remaining elements in the heap.
Edge cases: k = 0 (return original sum), all piles have 1 stone (removing half gives 0, total decreases by 1 per operation), single pile (repeatedly halve it k times).
Optimal Approach
Step 1: Build a max-heap from the piles (negate values for Python's min-heap).
Step 2: Repeat k times:
- Pop the largest value (negate to get positive)
- Compute removed = floor(value / 2)
- Push back (value - removed), negated
Step 3: Sum all remaining values in the heap (negate each).
Walkthrough for piles = [5, 4, 9], k = 2:
- Heap: [-9, -5, -4]. Total = 18.
- Op 1: pop -9 -> value=9. removed=floor(9/2)=4. remaining=5. Push -5. Heap: [-5, -5, -4].
- Op 2: pop -5 -> value=5. removed=floor(5/2)=2. remaining=3. Push -3. Heap: [-5, -4, -3].
- Sum: 5+4+3 = 12.
Time: O(n + k*log(n)) for building heap and k operations. Space: O(n) for the heap.
Max-heap keeps the biggest pile on top
What Trips People Up in Real Interviews
Using a min-heap instead of a max-heap. Python's heapq is a min-heap. Negate the values to simulate a max-heap: push -piles[i] and pop -result.
Forgetting that floor division applies after popping. floor(9/2) = 4, not 4.5. The remaining pile is 9 - 4 = 5, not 9 - 4.5 = 4.5. Always use integer division.
Not pushing the reduced pile back. After removing stones from the largest pile, the remaining stones must go back into the heap for future operations. Forgetting this means you lose track of the pile.
Computing the sum after each operation instead of at the end. You only need the final sum after k operations. Summing after each operation is wasteful and doesn't change the result.
Overflow with large pile values. If piles[i] can be up to 10^5 and k up to 10^5, the sum can be up to 10^10, which exceeds 32-bit int range. Use long long in C++ or long in Java for the total.
Solution Code
O(n + k log n) timeimport heapq
def minStoneSum(piles, k):
heap = [-p for p in piles]
heapq.heapify(heap)
for _ in range(k):
val = -heapq.heappop(heap)
heapq.heappush(heap, -(val - val // 2))
return -sum(heap)Frequently Asked Questions
What is the Remove Stones to Minimize the Total problem?
Given an array of piles where piles[i] represents the number of stones in the i-th pile, and an integer k, perform k operations. In each operation, remove half the stones (rounded down) from the pile with the most stones. Return the minimum total stones remaining after k operations.
How do you solve Remove Stones to Minimize the Total?
The optimal approach runs in O(n + k log n) time and O(n) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.
What companies ask Remove Stones to Minimize the Total?
Remove Stones to Minimize the Total is asked at Salesforce. It is a medium difficulty problem.
What are common mistakes on Remove Stones to Minimize the Total?
- Using a `min-heap` instead of a `max-heap`. Python's `heapq` is a min-heap. Negate the values to simulate a max-heap: push `-piles[i]` and pop `-result`.
- Forgetting that floor division applies after popping. `floor(9/2) = 4`, not 4.5. The remaining pile is `9 - 4 = 5`, not `9 - 4.5 = 4.5`. Always use integer division.
- Not pushing the reduced pile back. After removing stones from the largest pile, the remaining stones must go back into the heap for future operations. Forgetting this means you lose track of the pile.
- Computing the sum after each operation instead of at the end. You only need the final sum after k operations. Summing after each operation is wasteful and doesn't change the result.
- Overflow with large pile values. If `piles[i]` can be up to 10^5 and k up to 10^5, the sum can be up to 10^10, which exceeds 32-bit int range. Use `long long` in C++ or `long` in Java for the total.