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.
1function maxScore(nums, k) {
2 let maxHeap = new MaxPriorityQueue({ priority: x => x });
3 nums.forEach(num => maxHeap.enqueue(num));
4 let score = 0;
5
6 while (k > 0) {
7 let maxElem = maxHeap.dequeue().element;
8 score += maxElem;
9 let newValue = Math.ceil(maxElem / 3);
10 maxHeap.enqueue(newValue);
11 k--;
12 }
13 return score;
14}
15
16// Example Usage
17let nums = [1, 10, 3, 3, 3];
18let k = 3;
19console.log(maxScore(nums, k)); // Output: 17This JavaScript code employs a priority queue to repeatedly access the highest element, maximize the score, and apply the required transformation.
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.
1using System;
2using System.Collections.Generic;
3
4public class MaxScoreClass
5{
public static int MaxScore(int[] nums, int k)
{
// Using PriorityQueue from C# Collections
var maxHeap = new PriorityQueue<int, int>(Comparer<int>.Create((x, y) => y - x));
foreach (var num in nums) maxHeap.Enqueue(num, num);
int score = 0;
for (int i = 0; i < k; ++i)
{
int maxElem = maxHeap.Dequeue();
score += maxElem;
maxHeap.Enqueue((int)Math.Ceiling(maxElem / 3.0), (int)Math.Ceiling(maxElem / 3.0));
}
return score;
}
public static void Main()
{
int[] nums = { 1, 10, 3, 3, 3 };
int k = 3;
Console.WriteLine(MaxScore(nums, k)); // Output: 17
}
}The C# solution uses a priority queue to select and re-enqueue elements, optimized by a custom comparator to facilitate descending order behavior.