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:
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.
floor(x) is the greatest integer that is smaller than or equal to x (i.e., rounds x down).
Example 1:
Input: piles = [5,4,9], k = 2 Output: 12 Explanation: Steps of a possible scenario are: - Apply the operation on pile 2. The resulting piles are [5,4,5]. - Apply the operation on pile 0. The resulting piles are [3,4,5]. The total number of stones in [3,4,5] is 12.
Example 2:
Input: piles = [4,3,6,7], k = 3 Output: 12 Explanation: Steps of a possible scenario are: - Apply the operation on pile 2. The resulting piles are [4,3,3,7]. - Apply the operation on pile 3. The resulting piles are [4,3,3,4]. - Apply the operation on pile 0. The resulting piles are [2,3,3,4]. The total number of stones in [2,3,3,4] is 12.
Constraints:
1 <= piles.length <= 1051 <= piles[i] <= 1041 <= k <= 105The key idea of this approach is to use a max-heap (priority queue) to efficiently extract and update the largest pile each time. We repeatedly apply the operation on the largest pile, reducing it by floor(piles[i] / 2). Each time we remove the stones, we push the updated pile back into the max-heap for further operations until k operations are completed.
This Python solution uses the heapq library to maintain a max-heap (implemented as a min-heap with negative values). It performs k operations, each time reducing the largest pile. The final step returns the sum of the remaining piles.
Java
JavaScript
Time Complexity: O(k log n) where n is the number of piles. Space Complexity: O(n) due to the heap storage.
This approach involves using sorting to simulate the operations of a max-heap. The array of piles is repeatedly sorted to find the largest pile, then the operation is applied, and the sequence is repeated for k times.
This C solution uses qsort to sort the piles array in descending order in each iteration to simulate the max-heap top extraction. The largest element is reduced, and the process repeats for k times. Finally, it returns the sum of the left piles.
C#
Time Complexity: O(k n log n), Space Complexity: O(1) (in-place sort).
| Approach | Complexity |
|---|---|
| Approach 1: Use a Max-Heap for Efficient Pile Reduction | Time Complexity: O(k log n) where n is the number of piles. Space Complexity: O(n) due to the heap storage. |
| Approach 2: Simulate Heap with Sorting | Time Complexity: O(k n log n), Space Complexity: O(1) (in-place sort). |
Leetcode Remove Stones to Minimize the Total | weekly 253 • CodeinDepth • 2,401 views views
Watch 9 more video solutions →Practice Remove Stones to Minimize the Total with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor