1962. Remove Stones to Minimize the Total

📝 Problem Details

• Title: 1962. Remove Stones to Minimize the Total
• Link: https://leetcode.com/problems/remove-stones-to-minimize-the-total/
• Difficulty: Medium
• Tags/Categories: Arrays Greedy Priority-Queue

💭What Were My Initial Thoughts?

or each operation, we choose the element i with the highest value? 
therefore the floor calculation should result the biggest reduction in stones per iteration

🤔What Did I Struggle With?

the floor calculation is not 1:1 to the question description
integer division in C++ already floors the results, so floor is unecessary

💡 Explanation of Solution

init a priority queue iterate through piles, 
inserting it into the pq iterate k times, getting the max element from the pq, 
performing the floor calculation, 
pushing it back into the queue, and repeating k times

⌛ Complexity Analysis

Heap Init : O(n log n) for inserting all elements into the heap
Space Complexity: O(n)

💻 Implementation of Solution

class Solution {
 
public:
 
    int minStoneSum(vector<int>& piles, int k) {
        priority_queue<int> pq;
 
        for(int i=0; i < piles.size(); i++) {
            pq.push(piles[i]);
        }
 
        for(int i=0; i < k; i++) {
            int currLargest = pq.top();
            pq.pop();
            pq.push(currLargest - currLargest / 2);
        }
  
        int minTotal = 0;
  
        while(!pq.empty()){
            minTotal += pq.top();
            pq.pop();
        }
        return minTotal;
    }
};