Maximal score after applying k operations

January 9, 2023


Problem URL: Maximal score after applying k operations

We will use a heap to keep track of the maximum score. We will pop the maximum score from the heap and apply the operations to the popped score. We will push the new scores to the heap. We will repeat this process until we have applied all the operations.

class Solution:
    def maxKelements(self, nums: List[int], k: int) -> int:
        nums = [-n for n in nums]
        res = 0
        for _ in range(k):
            num = -1 * heapq.heappop(nums)
            res += num
            heapq.heappush(nums, -1 * math.ceil(num/3))
        return res

Time complexity: O(klog(n))
Space complexity: O(n)