Maximal Score After Applying K Operations — Medium Problem & Solution

Problem statement

Starting with a score of 0, you apply exactly k operations. Each operation picks an index i, adds nums[i] to the score, and then replaces nums[i] with ceil(nums[i] / 3).

Return the maximum score reachable. Here ceil(x / 3) is x / 3 rounded up.

Example 1

Input: nums = [10,10,10,10,10], k = 5
Output: 50
Explanation: Take each 10 once.

Example 2

Input: nums = [1,10,3,3,3], k = 3
Output: 17
Explanation: Take 10, which becomes 4; take 4, which becomes 2; take 3 — total 17.

Example 3

Input: nums = [7], k = 2
Output: 10
Explanation: Take 7, which becomes 3; then take the 3.

Constraints

• 1 <= nums.length <= 10^5
• 1 <= nums[i] <= 10^5
• 1 <= k <= 10^4

How to solve Maximal Score After Applying K Operations

Greedy with a max-heap: take the largest value k times, pushing back ceil(v / 3) each time.

Approach

1. Heapify the array into a max-heap.
2. Repeat k times: read the top, add it to the score, replace it with ceil(top / 3) and sift down.
3. Return the accumulated score.

Why it works

Taking the largest is safe because the operations are independent — reducing one entry never raises another — so at each step the biggest available value is the best possible gain, and no future step is worsened by it. Replacing the root in place and sifting down is one O(log n) operation instead of a pop plus a push.

Complexity

• Time — O(n + k log n)
• Space — O(n)

Pitfalls

• The division rounds up: use (v + 2) / 3 in integers.
• Plain sorting is not enough; the order changes after each operation.
• A single element can be taken repeatedly, shrinking each time.

Reference solution

Python

from typing import List
import heapq

def maxKelements(nums: List[int], k: int) -> int:
    heap = [-v for v in nums]
    heapq.heapify(heap)
    score = 0
    for _ in range(k):
        top = -heapq.heappop(heap)
        score += top
        heapq.heappush(heap, -((top + 2) // 3))
    return score

JavaScript

var maxKelements = function(nums, k) {
    var heap = nums.slice();
    var sift = function(j) {
        for (;;) {
            var l = 2 * j + 1, r = l + 1, s = j;
            if (l < heap.length && heap[l] > heap[s]) s = l;
            if (r < heap.length && heap[r] > heap[s]) s = r;
            if (s === j) break;
            var t = heap[s]; heap[s] = heap[j]; heap[j] = t;
            j = s;
        }
    };
    for (var i = Math.floor(heap.length / 2) - 1; i >= 0; i--) sift(i);
    var score = 0;
    for (var step = 0; step < k; step++) {
        var top = heap[0];
        score += top;
        heap[0] = Math.floor((top + 2) / 3);
        sift(0);
    }
    return score;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Minimum Number of Increments on Subarrays to Form a Target Array Medium
• Find the Winner of an Array Game Medium
• Queries on a Permutation With Key Medium
• Corporate Flight Bookings Medium
• Find the Winner of the Circular Game Medium
• Longest Subsequence With Limited Sum Medium