Remove Stones to Minimize the Total

Medium
1424.

Remove Stones to Minimize the Total

MediumArrayGreedyHeap (Priority Queue)AmazonGoogle

Remove Stones to Minimize the Total is a medium coding problem on arrays, greedy and heap, asked in Amazon and Google interviews.

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^5
  • 1 <= piles[i] <= 10^4
  • 1 <= k <= 10^5
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} piles
 * @param {number} k
 * @return {number}
 */
var minStoneSum = function(piles, k) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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^5
  • 1 <= piles[i] <= 10^4
  • 1 <= k <= 10^5

Hints for Remove Stones to Minimize the Total

  1. Hint 1

    An operation on a pile of size x removes floor(x / 2) stones — the bigger the pile, the bigger the saving.

  2. Hint 2

    Every operation is independent of the order the others happen in, so greedily take the largest saving available right now.

  3. Hint 3

    Keep the piles in a max-heap: pop the largest, push back x - floor(x / 2), k times, 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

  1. Put every pile size into a max-heap.
  2. Repeat k times: pop the largest size x and push x - floor(x / 2) back.
  3. 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 k operations 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