Maximal Score After Applying K Operations
Problem
Start with a score of 0. In one operation, pick any index i, add nums[i] to your score, then replace nums[i] with ceil(nums[i] / 3). Apply exactly k operations and return the maximum possible score.
Since adding a larger number always beats a smaller one, it is optimal to grab the current maximum every time — a perfect job for a max-heap (priority queue).
nums = [1,10,3,3,3], k = 317import heapq
def maxKelements(nums, k):
# Python's heapq is a MIN-heap, so store negatives.
heap = [-n for n in nums]
heapq.heapify(heap) # O(n) build
score = 0
for _ in range(k):
top = -heapq.heappop(heap) # current maximum
score += top # bank it
nxt = (top + 2) // 3 # ceil(top / 3)
heapq.heappush(heap, -nxt) # push the shrunk value back
return scorefunction maxKelements(nums, k) {
// Simple binary max-heap over numbers.
const heap = new MaxHeap();
for (const n of nums) heap.push(n); // build heap
let score = 0;
for (let i = 0; i < k; i++) {
const top = heap.pop(); // current maximum
score += top; // bank it
const nxt = Math.ceil(top / 3); // shrink
heap.push(nxt); // push it back
}
return score;
}long maxKelements(int[] nums, int k) {
// Max-heap of longs (values can grow during pushes).
PriorityQueue<Long> pq = new PriorityQueue<>(Collections.reverseOrder());
for (int n : nums) pq.offer((long) n); // build heap
long score = 0;
for (int i = 0; i < k; i++) {
long top = pq.poll(); // current maximum
score += top; // bank it
long nxt = (top + 2) / 3; // ceil(top / 3)
pq.offer(nxt); // push it back
}
return score;
}long long maxKelements(vector<int>& nums, int k) {
// Default priority_queue is a MAX-heap.
priority_queue<long long> pq(nums.begin(), nums.end());
long long score = 0;
for (int i = 0; i < k; i++) {
long long top = pq.top(); pq.pop(); // current maximum
score += top; // bank it
long long nxt = (top + 2) / 3; // ceil(top / 3)
pq.push(nxt); // push it back
}
return score;
}Explanation
This is a greedy problem with a clean argument: at every operation you add some element's current value to your score. A larger value always contributes more than a smaller one, and taking the largest now never hurts later choices (the others are untouched). So the optimal strategy is simply — always take the current maximum.
To repeatedly “take the maximum, shrink it, put it back” efficiently we use a max-heap (priority queue). It answers “what is the largest element?” in O(1) and supports removal/insertion in O(log n), which is exactly the operation mix we need.
Each of the k rounds does three things: pop the maximum top, add top to score, and push back ceil(top / 3). The ceiling is computed with integer math as (top + 2) / 3, which equals ⌈top / 3⌉ for positive integers.
Python's heapq is a min-heap, so we negate values to emulate a max-heap. Java uses Collections.reverseOrder(), and C++'s priority_queue is already a max-heap by default.
Example: nums = [1,10,3,3,3], k = 3. Take 10 (push 4), take 4 (push 2), take 3 (push 1). Score = 10 + 4 + 3 = 17. Because values can stay large across pushes, the running score is returned as a 64-bit integer.