Problem

You are given a 0-indexed integer array nums and an integer k. You have a starting score of 0.

In one operation:

  1. choose an index i such that 0 <= i < nums.length,
  2. increase your score by nums[i], and
  3. 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.

Examples

Example 1:

1
2
3

Input: nums = [10,10,10,10,10], k = 5
Output: 50
Explanation: Apply the operation to each array element exactly once. The final score is 10 + 10 + 10 + 10 + 10 = 50.

Example 2:

1
2
3
4
5
6
7

Input: nums = [1,10,3,3,3], k = 3
Output: 17
Explanation: You can do the following operations:
Operation 1: Select i = 1, so nums becomes [1,**4**,3,3,3]. Your score increases by 10.
Operation 2: Select i = 1, so nums becomes [1,**2**,3,3,3]. Your score increases by 4.
Operation 3: Select i = 2, so nums becomes [1,1,**1**,3,3]. Your score increases by 3.
The final score is 10 + 4 + 3 = 17.

Solution

Method 1 - Using MaxHeap

To achieve the maximum possible score after exactly k operations, you should focus on repeatedly selecting the largest possible values from nums as it will give the highest immediate score increments. Once a value is selected, it should be replaced by ceil(value / 3) to potentially be reused in subsequent operations, albeit with a reduced value.

Here is the approach:

  1. Use a Max-Heap:
    • Max-Heap is essential here because it allows us to always pick the largest element efficiently. In Python, the heapq module provides a min-heap, so we’ll need to insert negative values to simulate a max-heap behavior.
    • For Java, a PriorityQueue configured with a custom comparator can serve as a max-heap.
  2. Initialization:
    • Initialize the max-heap with all the elements from nums using their negative values for Python and natural ordering for Java to mimic a max-heap.
    • Maintain a variable, score, to accumulate the score from each operation.
  3. Operations:
    • For each of the k operations, extract the largest element from the heap, add its value to the score, compute the new value as ceil(value / 3), and push the new value back into the heap.
    • The ceil value can be calculated in constant time.
  4. Completion:
    • After completing k operations, return score.

Video explanation

Here is the video explaining this method in detail. Please check it out:

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

class Solution {
    public long maxKelements(int[] nums, int k) {
        // Create a max-heap using a priority queue with a custom comparator
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a, b) -> b - a);
        
        // Initialize the max-heap with all elements from the input array 'nums'
        for (int num : nums) {
            maxHeap.offer(num); // Add each element to the heap
        }
        
        // Initialize the score to 0
        long score = 0;
        
        // Perform k operations as described
        for (int i = 0; i < k; i++) {
            // Extract the largest element from the heap
            int largest = maxHeap.poll();
            
            // Add this largest element to the score
            score += largest;
            
            // Calculate the new value by dividing the largest element by 3 and taking the ceiling
            int newValue = (int) Math.ceil((double) largest / 3);
            
            // Add the new value back to the heap
            maxHeap.offer(newValue);
        }
        
        // Return the accumulated score after k operations
        return score;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

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

Complexity

  • ⏰ Time complexity: O(n + k log n), where n is the number of elements in nums. Each of the k operations involves extracting the maximum element and inserting a new element into the heap, both of which take O(log n) time.
  • 🧺 Space complexity: O(n), for storing elements in the heap.