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

Remove Stones to Minimize the Total

Difficulty: Medium

Problem Description

You are given a 0-indexed integer array piles, where piles[i] represents the number of stones in the ith pile, and an integer k. You should apply the following operation exactly k times:

  • Choose any piles[i] and remove floor(piles[i] / 2) stones from it.

Notice that you can apply the operation on the same pile more than once.

Return the minimum possible total number of stones remaining after applying the k operations.

Key Insights

  • The goal is to minimize the total number of stones remaining after k operations.
  • Each operation on a pile reduces its size by half (rounded down).
  • A greedy approach can be used to always operate on the pile with the maximum stones.
  • A priority queue (max-heap) can efficiently allow us to always access the largest pile.

Space and Time Complexity

Time Complexity: O(k log n), where n is the number of piles. Each of the k operations involves a logarithmic time complexity for heap operations.

Space Complexity: O(n) for storing the max-heap.

Solution

The problem can be solved using a max-heap data structure. The approach is as follows:

  1. Insert all elements of the piles array into a max-heap.
  2. For k times, extract the maximum pile, compute the number of stones to remove (floor(max / 2)), and push the updated pile size back into the heap.
  3. After performing all k operations, the total number of stones remaining is the sum of the elements in the heap.

This ensures that in each operation, we are always reducing the largest pile available, thus minimizing the total stones remaining effectively.

Code Solutions

import heapq

def min_stones(piles, k):
    # Create a max-heap using negative values since Python's heapq is a min-heap
    max_heap = [-pile for pile in piles]
    heapq.heapify(max_heap)
    
    for _ in range(k):
        # Pop the largest pile (negate back to get the original value)
        max_pile = -heapq.heappop(max_heap)
        # Calculate the new pile size after removing stones
        new_pile = max_pile - (max_pile // 2)
        # Push the updated pile size back into the heap
        heapq.heappush(max_heap, -new_pile)
    
    # Calculate the total remaining stones
    return -sum(max_heap)
← Back to All Questions