Leetcode Daily Question 14/10/2024 - 2530. Maximal Score After Applying K Operations

Problem Description:

You are given a 0-indexed integer array nums and an integer k. You have a starting score of 0. | ------------------------------------------------ | In one operation: | ------------------------------------------------ | choose an index i such that 0 <= i < nums.length, increase your score by nums[i], and replace nums[i] with ceil(nums[i] / 3). Return the maximum possible score you can attain after applying exactly k operations. | ------------------------------------------------ | The ceiling function ceil(val) is the least integer greater than or equal to val.

import heapq
from typing import List
class Solution:
  def maxKelements(self, nums: List[int]) -> int:
    max_heap = [-num for num in nums]
    heapq.heapify(max_heap)
    
    total = 0
    for _ in range(k):
      num = -heapq.heappop(max_heap)
      total += num
      heapq.heappush(max_heap, -math.ceil(num / 3))
    
    return total

Explanation:

Since we do not have restriction on the number of times we can choose an index, we can use a max heap to solve this.

The natural heap structure puts the smallest number on top. To create a max heap, we make all the numbers negative. Then the largest number will sit on the top of the heap.

To calculate the total, we pop from the heap, return it to its positive form and add it to the total. Then, we push the negative ceiling of num / 3 back into the heap as specified by the question.

Doing this k times guarantees that we will have the largest sum.

def maxKelements(nums):
  max_heap = [-num for num in nums]
  heapq.heapify(max_heap)
  
  total = 0
  for _ in range(k):
    num = -heapq.heappop(max_heap)
    total += num
    heapq.heappush(max_heap, -math.ceil(num / 3))
    
  return total

The time complexity is O(n + k log n) as building the heap takes O(n) time. Each heap operation takes O(log n) time, we do this k times.

The space complexity is O(n) as the heap has the same size as nums.

The full solution can be found near the top of the page.