Maximal Score After Applying K Operations
MedPrompt
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
isuch that0 <= i < nums.length, - increase your score by
nums[i], and - replace
nums[i]withceil(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.
Example 1:
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:
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,2,1,3,3]. Your score increases by 3.
The final score is 10 + 4 + 3 = 17.
Constraints:
1 <= nums.length, k <= 1051 <= nums[i] <= 109
Approaches
2 approaches with complexity analysis and trade-offs.
This approach directly simulates the process described in the problem. We perform k operations. In each operation, we find the largest number in the array by scanning through it, add this number to our score, and then replace it with its updated value.
Algorithm
- Initialize
score = 0. - Repeat
ktimes:- Find the index
maxIndexof the maximum element innumsby scanning the entire array. - Add
nums[maxIndex]toscore. - Update
nums[maxIndex] = ceil(nums[maxIndex] / 3).
- Find the index
- Return
score.
Walkthrough
This approach directly simulates the process described in the problem. We perform k operations. In each operation, we find the largest number in the array, add it to our score, and then replace it with its updated value.
The algorithm is as follows:
- Initialize a variable
scoreof typelongto 0. - Loop
ktimes. In each iterationifrom0tok-1:- Find the maximum element in the
numsarray. To do this, we can iterate through the array, keeping track of the maximum value found so far (maxVal) and its index (maxIndex). - Add
maxValto ourscore. - Update the element at
maxIndexwith the new value. The new value isceil(maxVal / 3). The ceiling ofa / bcan be calculated using floating-point mathMath.ceil((double)a / b)or integer arithmetic(a + b - 1) / b. For this problem,(maxVal + 2) / 3also works.
- Find the maximum element in the
- After the loop finishes,
scorewill hold the maximum possible score, which we return.
Here is the implementation in Java:
class Solution { public long maxKelements(int[] nums, int k) { long score = 0; for (int i = 0; i < k; i++) { int maxVal = -1; int maxIndex = -1; // Find the maximum element in the array for (int j = 0; j < nums.length; j++) { if (nums[j] > maxVal) { maxVal = nums[j]; maxIndex = j; } } // Add the max element to the score score += maxVal; // Update the element in the array nums[maxIndex] = (int) Math.ceil((double) maxVal / 3.0); } return score; }}Complexity
Time
O(k * n). The outer loop runs `k` times, and inside it, we scan the array of size `n` to find the maximum. This results in `k * n` operations. For the given constraints (`k, n <= 10^5`), this would be too slow.
Space
O(1). We are modifying the input array in-place and using only a few extra variables, so the auxiliary space is constant.
Trade-offs
Pros
Simple to understand and implement.
Very low memory usage as it modifies the array in-place.
Cons
Highly inefficient for large
kandn.Will likely result in a "Time Limit Exceeded" error on most competitive programming platforms.
The problem can be solved greedily. To maximize the total score, we should always pick the largest available number at each step. Finding the maximum element repeatedly is a task well-suited for a max-heap data structure (implemented as a Priority Queue in Java).
Algorithm
- Create a max-priority queue.
- Add all elements from
numsinto the priority queue. - Initialize
score = 0. - Repeat
ktimes:- Remove the top element (maximum) from the priority queue. Let it be
maxVal. - Add
maxValtoscore. - Calculate
newVal = ceil(maxVal / 3). - Add
newValback to the priority queue.
- Remove the top element (maximum) from the priority queue. Let it be
- Return
score.
Walkthrough
A max-heap is a perfect data structure for this problem because it allows for efficient retrieval of the maximum element. We can use it to maintain the numbers from the nums array and always have quick access to the largest one. In Java, this is implemented using a PriorityQueue.
The algorithm is as follows:
- Create a max-heap. In Java, a
PriorityQueueis a min-heap by default, so we provide a reverse order comparator (Collections.reverseOrder()) to simulate a max-heap. - Populate the max-heap with all the elements from the input
numsarray. - Initialize a
longvariablescoreto 0. - Loop
ktimes:- Extract the maximum element from the heap using the
poll()method. This element is the largest number currently available. - Add this extracted element to
score. - Calculate the new value after the operation:
newVal = ceil(element / 3). - Insert this
newValback into the heap using theadd()method. The heap property will be maintained automatically.
- Extract the maximum element from the heap using the
- After
kiterations, thescorevariable will contain the maximum possible score.
Here is the implementation in Java:
import java.util.Collections;import java.util.PriorityQueue; class Solution { public long maxKelements(int[] nums, int k) { // PriorityQueue is a min-heap by default, so use Collections.reverseOrder() // to make it a max-heap. PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder()); // Add all elements to the max-heap. for (int num : nums) { maxHeap.add(num); } long score = 0; for (int i = 0; i < k; i++) { // Get the current largest element. int maxVal = maxHeap.poll(); // Add it to the score. score += maxVal; // Calculate the new value and add it back to the heap. int newVal = (int) Math.ceil((double) maxVal / 3.0); maxHeap.add(newVal); } return score; }}Complexity
Time
O(n + k log n). Building the max-heap from `n` elements takes O(n) time (using heapify). The loop runs `k` times, and each iteration involves a `poll()` and an `add()` operation, both of which take O(log n) time. The total time is O(n + k log n).
Space
O(n). The priority queue needs to store all `n` elements from the input array.
Trade-offs
Pros
Highly efficient and will pass within the time limits for the given constraints.
It's the standard and optimal way to solve problems that require repeatedly finding/removing the min/max element from a collection.
Cons
Uses extra space proportional to the size of the input array to store the heap.
Solutions
Solution
class Solution {public long maxKelements(int[] nums, int k) { PriorityQueue<Integer> pq = new PriorityQueue<>((a, b)->b - a); for (int v : nums) { pq.offer(v); } long ans = 0; while (k-- > 0) { int v = pq.poll(); ans += v; pq.offer((v + 2) / 3); } return ans; }}class Solution: def maxKelements(self, nums: List[int], k: int) -> int: h = [- v for v in nums] heapify(h) ans = 0 for _ in range(k): v = - heappop(h) ans += v heappush(h, - (ceil(v / 3))) return ansclass Solution {public: long long maxKelements(vector<int> &nums, int k) { priority_queue<int> pq(nums.begin(), nums.end()); long long ans = 0; while (k--) { int v = pq.top(); pq.pop(); ans += v; pq.push((v + 2) / 3); } return ans; }};Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.