DEV Community

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

Posted on • Edited on

2530. Maximal Score After Applying K Operations

2530. Maximal Score After Applying K Operations

Difficulty: Medium

Topics: Array, Greedy, Heap (Priority Queue)

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

Hint:

  1. It is always optimal to select the greatest element in the array.
  2. Use a heap to query for the maximum in O(log n) time.

Solution:

Let's break down the solution for the "Maximal Score After Applying K Operations" problem:

Approach:

  1. Use a Max Heap: The problem requires us to maximize the score by selecting the largest available number in nums for k operations. A Max Heap (priority queue) is ideal here since it allows us to efficiently extract the largest element and then insert updated values.

  2. Extract the Maximum Element: For each operation, extract the largest element from the heap. This element will be added to the score.

  3. Update the Extracted Element: After using the largest element, replace it with ceil(num / 3) (rounding up). This simulates the reduction in the value of the chosen element as per the problem's requirement.

  4. Insert the Updated Element Back into the Heap: Insert the updated value back into the heap so that it can be used in subsequent operations if it remains among the largest values.

  5. Repeat for k Operations: Perform this process exactly k times to ensure the maximum possible score is achieved after k operations.

Detailed Explanation:

  • Initialization:

    • SplMaxHeap is used to maintain a max-heap (priority queue) to efficiently get the maximum element at each step.
    • ans keeps track of the cumulative score.
    • Insert all elements of nums into the max heap.
  • Processing Each Operation:

    • Extract the largest element using extract().
    • Add this value to the sum.
    • Calculate the new value of this element as ceil(t / 3). Since PHP int division rounds down, we use (int)($t + 2) / 3 to simulate the ceiling.
    • Insert the updated value back into the heap.
  • Return the Final Score: After k operations, return the accumulated sum.

Let's implement this solution in PHP: 2530. Maximal Score After Applying K Operations

<?php
/**
 * @param Integer[] $nums
 * @param Integer $k
 * @return Integer
 */
function maxKelements($nums, $k) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}
?>
Enter fullscreen mode Exit fullscreen mode

Example Walkthrough:

Example 1: nums = [10, 10, 10, 10, 10], k = 5

  • Initial Heap: [10, 10, 10, 10, 10]
  • Extract 10, score += 10, insert ceil(10/3) = 4: New Heap: [10, 10, 10, 10, 4]
  • Extract 10, score += 10, insert ceil(10/3) = 4: New Heap: [10, 10, 4, 10, 4]
  • Repeat similarly for all elements. The final score will be 50.

Example 2: nums = [1, 10, 3, 3, 3], k = 3

  • Initial Heap: [10, 3, 3, 3, 1]
  • Extract 10, score += 10, insert ceil(10/3) = 4: New Heap: [4, 3, 3, 3, 1]
  • Extract 4, score += 4, insert ceil(4/3) = 2: New Heap: [3, 3, 3, 2, 1]
  • Extract 3, score += 3, insert ceil(3/3) = 1: New Heap: [3, 3, 2, 1, 1]
  • Final score is 17.

Complexity:

  • Time Complexity: O(k log n), where k is the number of operations and n is the size of the heap. Each extraction and insertion operation on the heap takes O(log n) time, and this is done k times.
  • Space Complexity: O(n) for storing the elements in the max heap.

This solution efficiently maximizes the score by always choosing the largest available number and managing the decreasing values using a priority queue.

Contact Links

If you found this series helpful, please consider giving the repository a star on GitHub or sharing the post on your favorite social networks 😍. Your support would mean a lot to me!

If you want more helpful content like this, feel free to follow me:

Image of AssemblyAI

Automatic Speech Recognition with AssemblyAI

Experience near-human accuracy, low-latency performance, and advanced Speech AI capabilities with AssemblyAI's Speech-to-Text API. Sign up today and get $50 in API credit. No credit card required.

Try the API

Top comments (0)

AWS Security LIVE!

Tune in for AWS Security LIVE!

Join AWS Security LIVE! for expert insights and actionable tips to protect your organization and keep security teams prepared.

Learn More

👋 Kindness is contagious

Discover a treasure trove of wisdom within this insightful piece, highly respected in the nurturing DEV Community enviroment. Developers, whether novice or expert, are encouraged to participate and add to our shared knowledge basin.

A simple "thank you" can illuminate someone's day. Express your appreciation in the comments section!

On DEV, sharing ideas smoothens our journey and strengthens our community ties. Learn something useful? Offering a quick thanks to the author is deeply appreciated.

Okay