Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/2530.html

2530. Maximal Score After Applying K Operations

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

Solutions

• Java
• C++
• Python
• Go
• TypeScript
• RenderScript

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

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

• 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
  
  

• 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(interface{})     {}
  func (hp) Pop() (_ interface{}) { return }
  

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

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

All Problems

All Solutions