Follow

# .css-ecb9sr{display:-webkit-box;display:-webkit-flex;display:-ms-flexbox;display:flex;-webkit-flex-direction:row;-ms-flex-direction:row;flex-direction:row;-webkit-align-items:center;-webkit-box-align:center;-ms-flex-align:center;align-items:center;width:16rem;}  Follow  Photo by Nick Morrison on Unsplash

# 1962. Remove Stones to Minimize the Total

Kumar Pallav
·Dec 28, 2022·

• Explanation
• Approach
• Code

To solve the question you can visit the following link

## Explanation

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

## Approach

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.

## Code

``````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
while(k!=0){
int top= pq.poll();
k--;
}
int result=0;
// Sum of remaining is our answer.
while(!pq.isEmpty()){
result+=pq.remove();
}
return result;
}
}
``````