2530. Maximal Score After Applying K Operations

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,1,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

Approach 01

#include <queue>
#include <vector>
#include <cmath>

class Solution {
public:
    long long maxKelements(std::vector<int>& numbers, int k) {
        long long result = 0;  // Use long long for larger sums
        std::priority_queue<int> maxHeap(numbers.begin(), numbers.end());

        for (int i = 0; i < k; ++i) {
            int currentNumber = maxHeap.top();
            maxHeap.pop();
            result += currentNumber;
            // Push the next number (ceiling of currentNumber / 3) back into the heap
            maxHeap.push(static_cast<int>(std::ceil(currentNumber / 3.0)));
        }

        return result;
    }
};

import heapq
import math
from typing import List

class Solution:
    def maxKelements(self, numbers: List[int], k: int) -> int:
        result = 0
        negNumbers = [-n for n in numbers]
        heapq.heapify(negNumbers)

        for _ in range(k):
            currentNumber = -heapq.heappop(negNumbers)
            result += currentNumber
            heapq.heappush(negNumbers, -math.ceil(currentNumber / 3))

        return result

Time Complexity

• Building the max heap:

  Constructing a max heap from the input array takes \(O(n)\), where n is the number of elements in the array.

• Iterating and updating the heap:

  For each of the k iterations, the algorithm performs a pop and push operation on the heap. Both operations take \(O(\log n)\) time. Thus, the total time for these k iterations is \(O(k \log n)\).

• Overall Time Complexity:

  The overall time complexity is \(O(n + k \log n)\), where n is the size of the input array and k is the number of operations performed.

Space Complexity

• Heap Storage:

  The max heap stores all n elements from the input array, so it requires \(O(n)\) space.

• Auxiliary Space:

  Aside from the heap, the algorithm uses a constant amount of extra space for variables like result and currentNumber.

• Overall Space Complexity:

  The space complexity is \(O(n)\), where n is the size of the input array.