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

Remove Stones to Minimize the Total

Number: 2094

Difficulty: Medium

Paid? No

Companies: Nvidia

Problem Description

Given an array of piles where each element represents the number of stones in that pile, and an integer k, perform exactly k operations. In each operation, choose any pile and remove floor(pile / 2) stones from it. The goal is to minimize the total number of stones remaining after exactly k operations.

Key Insights

  • The best strategy is to always perform the operation on the pile with the maximum number of stones to achieve the maximum reduction in total stones.
  • A max-heap is ideal to constantly retrieve the pile with the maximum number of stones.
  • After each removal, update the pile and reinsert it into the heap for possible future operations.
  • The operation removes floor(pile / 2) stones, so the new number of stones becomes: pile - floor(pile / 2).

Space and Time Complexity

Time Complexity: O(k log n) where n is the number of piles.
Space Complexity: O(n) for the heap.

Solution

We use a max-heap (simulated using a min-heap with negated values) to always pick the pile with the highest number of stones. For each of the k operations:

  1. Extract the maximum pile.
  2. Compute the number of stones to be removed as floor(maxPile/2).
  3. Subtract the computed value and update the pile.
  4. Reinsert the updated pile back into the heap. After k operations, sum up all the remaining stones.

Code Solutions

import heapq

def minStoneSum(piles, k):
    # Convert piles into a max-heap by inserting negative values.
    max_heap = [-pile for pile in piles]
    heapq.heapify(max_heap)
    
    # Perform k operations
    for _ in range(k):
        # Get the pile with the most stones (invert sign to get the original value)
        max_pile = -heapq.heappop(max_heap)
        # Calculate stones to remove: floor(max_pile / 2)
        stones_removed = max_pile // 2
        # Update pile count after removal
        new_pile = max_pile - stones_removed
        # Push the updated pile back onto the heap (remember to negate)
        heapq.heappush(max_heap, -new_pile)
    
    # Sum up all remaining stones (invert sign again)
    return -sum(max_heap)

# Example usage:
piles = [5, 4, 9]
k = 2
print(minStoneSum(piles, k))  # Output: 12
← Back to All Questions