LeetCode 2530. Maximal Score After Applying K Operations Solution in Java, C++, Python & More | Explanation + Code

Description

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

Solutions

Solution 1: Priority Queue (Max Heap)

To maximize the sum of scores, we need to select the element with the maximum value at each step. Therefore, we can use a priority queue (max heap) to maintain the element with the maximum value.

At each step, we take out the element with the maximum value v from the priority queue, add v to the answer, and replace v with \lceil ^v⁄₃ \rceil, and then add it to the priority queue. After repeating this process k times, we return the answer.

The time complexity is O(n + k × log n), and the space complexity is O(n) or O(1). Here, n is the length of the array nums.

PythonJavaC++GoTypeScriptRust

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(code-box)

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; } }(code-box)

class Solution { public: long long maxKelements(vector<int>& nums, int k) { priority_queue<int> 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; } };(code-box)

func maxKelements(nums []int, k int) (ans int64) { h := hp{nums} heap.Init(&h) for ; k > 0; k-- { ans += int64(h.IntSlice[0]) h.IntSlice[0] = (h.IntSlice[0] + 2) / 3 heap.Fix(&h, 0) } return } type hp struct{ sort.IntSlice } func (h hp) Less(i, j int) bool { return h.IntSlice[i] > h.IntSlice[j] } func (hp) Push(any) {} func (hp) Pop() (_ any) { return }(code-box)

function maxKelements(nums: number[], k: number): number { const pq = new MaxPriorityQueue<number>(); nums.forEach(num => pq.enqueue(num)); let ans = 0; while (k > 0) { const v = pq.dequeue(); ans += v; pq.enqueue(Math.floor((v + 2) / 3)); k--; } return ans; }(code-box)

use std::collections::BinaryHeap; impl Solution { pub fn max_kelements(nums: Vec<i32>, k: i32) -> i64 { let mut pq = BinaryHeap::from(nums); let mut ans = 0; let mut k = k; while k > 0 { if let Some(v) = pq.pop() { ans += v as i64; pq.push((v + 2) / 3); k -= 1; } } ans } }(code-box)