1962. Remove Stones to Minimize the Total

To solve the question you can visit the following link

https://leetcode.com/problems/remove-stones-to-minimize-the-total/

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)
            pq.add(num);        
     //Iterate for K times and half the number of piles at top    
        while(k!=0){
             int top= pq.poll();
            pq.add((int) Math.ceil((float)top/2 ));
            k--;
        }
        int result=0;
// Sum of remaining is our answer.
        while(!pq.isEmpty()){
            result+=pq.remove();
        }
    return result;
    }
}

1962. Remove Stones to Minimize the Total

Comments

Data Structure & Algorithms

3Sum Closest - Step-by-Step with Java

More from this blog

Spring AI Tool Calling: From Chatbot to AI Agent with @Tool

Spring AI Advisors API in Java: Build Middleware for AI Interactions

Working with Multiple AI Models in Spring AI — @Qualifier, mutate(), and Model Routing

Spring AI ChatClient API: The Fluent Heart of AI Integration

What is Spring AI? — Why Java Developers Need This in 2026

Explanation

Approach

Code

Command Palette

Comments

Data Structure & Algorithms

3Sum Closest - Step-by-Step with Java

More from this blog

Explanation

Approach

Code