Scale Engineer

Maximal Score After Applying K Operations

Med
#2310Time: 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.1 company
Patterns
Greedy
Data structures
ArrayHeap (Priority Queue)
Companies
McKinsey

Prompt

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

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 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.

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:

  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:

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 k and n.

  • Will likely result in a "Time Limit Exceeded" error on most competitive programming platforms.

Solutions

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;  }}

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.

← Previous

Previous problem

Next →

Next problem