1962. Remove Stones to Minimize the Total

Photo by Nick Morrison on Unsplash

1962. Remove Stones to Minimize the Total

Kumar Pallav's photo
Kumar Pallav
·Dec 28, 2022·

2 min read

Table of contents

  • Explanation
  • Approach
  • Code

To solve the question you can visit the following link


The question is asking us to do one operation at a time, the operation is simply to reduce the number of piles to half. We can do at most K operations. We wan't to operate in a way that we minimize the number of piles after K operation.

We need to remove the maximum number of possible stones from the pipes which also means we need to operate on the maximum number of stones at any pile at any given time. The piles are kept in an unordered way which should be sorted but the problem with sorting the pile is that after removing the half, the pile will again become unsorted. So after each removal, we need to know which Pile has the maximum number of stones present.

The Data structure which can keep the max element always at the top is Max Heap. Let's look at the approach to solving it using Max Heap


We will put the elements (piles) on a Max Heap. At top of the max heap, we will have the pile with most of the elements. We will remove half of the pile, We will add half of the pile back to Max Heap.

We will keep doing the operation K times, whatever is left on the queue, the sum of it is our answer.


class Solution {
    public int minStoneSum(int[] piles, int k) {
//Create a PriorityQueue
    PriorityQueue<Integer> pq = new PriorityQueue<Integer>((a, b) -> b - a);
// Add all elements to PriorityQueue
         for(int num: piles)
     //Iterate for K times and half the number of piles at top    
             int top= pq.poll();
            pq.add((int) Math.ceil((float)top/2 ));
        int result=0;
// Sum of remaining is our answer.
    return result;

Did you find this article valuable?

Support Kumar Pallav by becoming a sponsor. Any amount is appreciated!

Learn more about Hashnode Sponsors
Share this