hi, let Avik connect you.


** You can give your thought about this content and request modifications if needed from Ask For Modifications page. Thank You.

** You can check all the posts on the Posts page.

** More about me in the About Me section.

Remove Stones to Minimize the Total


  • Approach:

    1. Take a MaxHeap (priority_queue).

    2. Insert all the stones of each pile into that MaxHeap and sum up the number of stones in each pile say, totalStones.

    3. Now keep looping until either the MaxHeap becomes empty or K remains in the hand.

    4. Extract the top element from the MaxHeap. Divide it by 2.

    5. Insert the rest of the top element into MaxHeap.

    6. Reduce the amount from totalStones.

    7. Return totalStones at the end.


  • Time and Space Complexity:

      • Time Complexity: O(Nlog2N)

      • Space Complexity: O(N)


Code [C++]

class Solution {

public:

int minStoneSum(vector<int>& piles, int k) {

priority_queue<int>pileHeap;

int totalStones = 0, n = piles.size();

for(int i=0; i<n; i++){

totalStones += piles[i];

pileHeap.push(piles[i]);

}

while((!pileHeap.empty() && k)){

int topPile = pileHeap.top();

pileHeap.pop();

totalStones -= topPile/2;

topPile -= (topPile/2);

if(topPile) pileHeap.push(topPile);

k--;

}

return totalStones;

}

};