DEV Community

Cover image for 2530. Maximal Score After Applying K Operations
MD ARIFUL HAQUE
MD ARIFUL HAQUE

Posted on

2530. Maximal Score After Applying K Operations

2530. Maximal Score After Applying K Operations

Medium

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

Solution:

class Solution {

    /**
     * @param Integer[] $nums
     * @param Integer $k
     * @return Integer
     */
    function maxKelements($nums, $k) {
        $pq = new SplMaxHeap(); // Building Max Heap
        $ans = 0;
        foreach($nums as $num){
            $pq->insert($num);
        }
        $sum = 0;
        for($i=0; $i<$k; $i++){
            $t = $pq->extract();
            $sum += (int)$t;
            $pq->insert((int)($t+2)/3); // taking ceil value
        }
        return $sum;
    }
}
Enter fullscreen mode Exit fullscreen mode

Contact Links

Top comments (0)