# Maximal Score After Applying K Operations **Difficulty:** MEDIUM [External](https://leetcode.com/problems/maximal-score-after-applying-k-operations) Canonical: https://scaleengineer.com/dsa/problems/maximal-score-after-applying-k-operations **Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy) **Data structures:** Array, Heap (Priority Queue) **Companies:** [McKinsey](https://scaleengineer.com/companies/mckinsey) --- ## 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`. **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 <= 105` * `1 <= nums[i] <= 109` # Approaches ## Brute Force Simulation 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. **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. **Pros:** Simple to understand and implement.; Very low memory usage as it modifies the array in-place. **Cons:** Highly inefficient for large `k` and `n`.; Will likely result in a "Time Limit Exceeded" error on most competitive programming platforms. ### Explanation 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: 1. Initialize a variable `score` of type `long` to 0. 2. Loop `k` times. In each iteration `i` from `0` to `k-1`: * Find the maximum element in the `nums` array. To do this, we can iterate through the array, keeping track of the maximum value found so far (`maxVal`) and its index (`maxIndex`). * Add `maxVal` to our `score`. * Update the element at `maxIndex` with the new value. The new value is `ceil(maxVal / 3)`. The ceiling of `a / b` can be calculated using floating-point math `Math.ceil((double)a / b)` or integer arithmetic `(a + b - 1) / b`. For this problem, `(maxVal + 2) / 3` also works. 3. After the loop finishes, `score` will hold the maximum possible score, which we return. Here is the implementation in Java: ```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; } } ``` ### Algorithm * Initialize `score = 0`. * Repeat `k` times: 1. Find the index `maxIndex` of the maximum element in `nums` by scanning the entire array. 2. Add `nums[maxIndex]` to `score`. 3. Update `nums[maxIndex] = ceil(nums[maxIndex] / 3)`. * Return `score`. ## Greedy Approach with Max-Heap 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). **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. **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. ### Explanation 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: 1. Create a max-heap. In Java, a `PriorityQueue` is a min-heap by default, so we provide a reverse order comparator (`Collections.reverseOrder()`) to simulate a max-heap. 2. Populate the max-heap with all the elements from the input `nums` array. 3. Initialize a `long` variable `score` to 0. 4. Loop `k` times: * 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 `newVal` back into the heap using the `add()` method. The heap property will be maintained automatically. 5. After `k` iterations, the `score` variable will contain the maximum possible score. Here is the implementation in Java: ```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 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; } } ``` ### Algorithm * Create a max-priority queue. * Add all elements from `nums` into the priority queue. * Initialize `score = 0`. * Repeat `k` times: 1. Remove the top element (maximum) from the priority queue. Let it be `maxVal`. 2. Add `maxVal` to `score`. 3. Calculate `newVal = ceil(maxVal / 3)`. 4. Add `newVal` back to the priority queue. * Return `score`. # Solutions ### Java ```java class Solution { public long maxKelements(int[] nums, int k) { PriorityQueue 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; } } ``` ### Python ```python 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 ans ``` ### CPP ```cpp class Solution { public: long long maxKelements(vector &nums, int k) { priority_queue 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; } }; ```