Sponsored
Sponsored
By using a max-heap (priority queue), we can efficiently select the largest element from the array in each operation. This strategy maximizes the immediate score increase. Once an element is chosen, reinsert it into the heap with its updated value (after applying the ceiling function of division by 3) so it can be considered for future operations.
Time Complexity: O(k log n) - Each heap operation (insert/extract) takes O(log n) and we perform it 'k' times.
Space Complexity: O(n) - Due to the heap storage.
1#include <iostream>
2#include <queue>
3#include <cmath>
4
5int maxScore(std::vector<int>& nums, int k) {
6 std::priority_queue<int> maxHeap(nums.begin(), nums.end());
7 int score = 0;
8
9 for (int i = 0; i < k; ++i) {
10 int max_elem = maxHeap.top();
11 maxHeap.pop();
12 score += max_elem;
13 int new_value = std::ceil(static_cast<double>(max_elem) / 3);
14 maxHeap.push(new_value);
15 }
16
17 return score;
18}
19
20// Example Usage
21int main() {
22 std::vector<int> nums = {1, 10, 3, 3, 3};
23 int k = 3;
24 std::cout << maxScore(nums, k) << std::endl; // Output: 17
25 return 0;
26}The C++ solution uses a priority queue to pick the largest number, exploit its value for scores, and push back the transformed number for further consideration.
Sort the array in descending order and apply the operation greedily by always picking elements from the start of the array for maximum immediate score increase. Re-insert the updated elements after processing through their div-3 transformation.
Time Complexity: O(k log n) - Efficient dealing with priorities during extraction and insertion.
Space Complexity: O(n) - Storing elements in the priority queue for processing.
1import java.util.*;
2
3
In Java, we utilize a priority queue configured for descending order to ensure the extraction of the current highest integer for scoring before updating and reinserting it.