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.