< Back





1962. Remove Stones to Minimize the Total

Given an array of piles, piles[i] represents the number of stones in the ith pile. For exactly k
operations, we can choose any pile and halve it. We want to minimize the total number of stones in
the piles after k operations.

We use a max heap to maintain the largest pile at heap[0]. During each operation, we halve the
largest pile and put it back into the heap. We then repeat this process k times. We then return the
sum of the piles.

The solution is as follows:


  from heapq import *
  from math import ceil

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

          for i in range(k):
              heappush(piles, -(ceil(-heappop(piles) / 2)))

          return sum([-pile for pile in piles])


_ Time Complexity:

  O(n + k * log n) - Heap operations take O(log n) time, we process n piles and perform k
  operations.

_ Space Complexity:

  O(n) - We maintain a heap of all piles.