Problem of The Day: Remove Stones to Minimize the Total

Problem Statement

leetcode problem link

Max Heap Approach [Accepted]

class Solution:
    def minStoneSum(self, piles: List[int], k: int) -> int:
        max_heap = []
        for pile in piles:
            heapq.heappush(max_heap, -pile)

        for _ in range(k):
            pile = heapq.heappop(max_heap)
            new_pile = math.ceil(-pile / 2)
            heapq.heappush(max_heap, -new_pile)
        return sum([-x for x in max_heap])

Editorial

Approach: Greedy + Max Heap

import heapq

class Solution:
    def minStoneSum(self, piles: List[int], k: int) -> int:
        heap = [-num for num in piles]
        heapq.heapify(heap)

        for _ in range(k):
            curr = -heapq.heappop(heap)
            remove = curr // 2
            heapq.heappush(heap, -(curr - remove))

        return -sum(heap)