We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Maximal Score After Applying K Operations

Difficulty: Medium

Problem Description

You are given a 0-indexed integer array nums and an integer k. You have a starting score of 0. In one operation, you can choose an index i, increase your score by nums[i], and replace nums[i] with ceil(nums[i] / 3). Return the maximum possible score you can attain after applying exactly k operations.

Key Insights

  • Each operation allows you to gain points from the current value in the array and then reduces that value significantly.
  • To maximize the score, you should always choose the largest available number in the array for each operation.
  • Using a max-heap (or priority queue) allows efficient retrieval of the largest number.
  • After each operation, the modified value must be pushed back into the heap for future operations.

Space and Time Complexity

Time Complexity: O(k log n)
Space Complexity: O(n)

Solution

To solve the problem, we can use a max-heap (priority queue) to efficiently manage the current maximum value in the nums array. The steps to achieve the solution are as follows:

  1. Insert all elements of the nums array into a max-heap.
  2. For k operations, perform the following:
    • Extract the maximum value from the heap.
    • Increase the score by that value.
    • Calculate the new value after applying the operation (using the ceiling of the division by 3).
    • Insert the new value back into the heap.
  3. After k operations, return the total score.

Code Solutions

import heapq
import math

def maximalScore(nums, k):
    # Create a max-heap by negating the values
    max_heap = [-num for num in nums]
    heapq.heapify(max_heap)
    
    score = 0
    for _ in range(k):
        # Get the maximum value (negate to get the original value)
        max_value = -heapq.heappop(max_heap)
        score += max_value
        # Calculate the new value after the operation
        new_value = math.ceil(max_value / 3)
        # Push the new value back into the max-heap
        heapq.heappush(max_heap, -new_value)
    
    return score
← Back to All Questions