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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Maximal Score After Applying K Operations

Number: 2616

Difficulty: Medium

Paid? No

Companies: Amazon, Google, TikTok, McKinsey

Problem Description

You are given an integer array nums and an integer k. Starting with a score of 0, you perform exactly k operations. In each operation, you select an index i, add nums[i] to your score, and then replace nums[i] with ceil(nums[i] / 3). The goal is to maximize the final score.

Key Insights

  • Always choose the element with the maximum value, since it provides the largest immediate boost to the score.
  • After selecting an element, its value decreases (via ceil division by 3), but reusing it later might still be beneficial.
  • A max-heap (or priority queue) is ideal for efficiently retrieving the maximum value at each operation.
  • The greedy strategy of always picking the largest available value is optimal for this problem.

Space and Time Complexity

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

Solution

To solve this problem, we use a max-heap data structure to always extract the largest number from the array efficiently. The algorithm follows these steps:

  1. Insert all elements of nums into a max-heap.
  2. For k operations:
    • Retrieve and remove the maximum element from the heap.
    • Add its value to the score.
    • Compute the new value as ceil(maxValue / 3) and insert it back into the heap.
  3. Return the accumulated score after k operations.

This approach guarantees that you always add the maximum possible value to your score at every operation, leading to an optimal solution.

Code Solutions

import heapq
import math

def maxScore(nums, k):
    # Convert to a max-heap by pushing negative values
    max_heap = [-num for num in nums]
    heapq.heapify(max_heap)
    
    score = 0
    for _ in range(k):
        # Extract the largest number (as negative)
        current = -heapq.heappop(max_heap)
        score += current  # Add it to the score
        # Compute new value after ceil division by 3
        new_value = math.ceil(current / 3)
        # Push the new value (as negative) back into the heap
        heapq.heappush(max_heap, -new_value)
    
    return score

# Example usage:
# print(maxScore([10,10,10,10,10], 5))
← Back to All Questions