Remove Stones to Minimize the Total — LeetCode 1962 Python Solution

The problem

You are given a 0-indexed integer array piles, where piles[i] represents the number of stones in the ith pile, and an integer k. You should apply the following operation exactly k times: Choose any piles[i] and remove floor(piles[i] / 2) stones from it.

Example

Input

piles = [5,4,9], k = 2

Output

12

Explanation

Steps of a possible scenario are:

Python solution

class Solution:
    def minStoneSum(self, piles: List[int], k: int) -> int:
        pq = [-x for x in piles]
        heapify(pq)
        for _ in range(k):
            heapreplace(pq, pq[0] // 2)
        return -sum(pq)

Complexity

Pattern: Heap / Priority Queue

Keep only the best k elements, or always pull the smallest, in log time. LeetCode 1962. Remove Stones to Minimize the Total is filed here because LeetCode tags it Heap (Priority Queue), which is the vocabulary this hub collects.

The heap / priority queue guide has the Python template for the pattern and the 163 LeetCode problems that use it.

Related problems