Sponsored
Sponsored
The 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.
Time Complexity: O(k log n) where n is the number of piles. Space Complexity: O(n) due to the heap storage.
1import heapq
2
3def min_stone_sum(piles, k):
4 max_heap = [-pile for pile in piles] # Use negative values to simulate max-heap
5 heapq.heapify(max_heap)
6
7 for _ in range(k):
8 largest = -heapq.heappop(max_heap)
9 reduced = largest - largest // 2
10 heapq.heappush(max_heap, -reduced)
11
12 return -sum(max_heap)
13
14# Example usage:
15print(min_stone_sum([5, 4, 9], 2)) # Output: 12
16print(min_stone_sum([4, 3, 6, 7], 3)) # Output: 12This 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.
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.
Time Complexity: O(k n log n), Space Complexity: O(1) (in-place sort).
1using System;
2using System.Linq;
3
4public class StoneRemoval {
5 public int MinStoneSum(int[] piles, int k) {
6 for (int i = 0; i < k; i++) {
Array.Sort(piles);
Array.Reverse(piles); // Max element at piles[0]
piles[0] -= piles[0] / 2;
}
return piles.Sum();
}
// Example usage
public static void Main() {
StoneRemoval sr = new StoneRemoval();
Console.WriteLine(sr.MinStoneSum(new int[]{5, 4, 9}, 2)); // Output: 12
Console.WriteLine(sr.MinStoneSum(new int[]{4, 3, 6, 7}, 3)); // Output: 12
}
}The C# solution applies sorting in each step to emulate the max-heap behavior. After sorting, it halves the effect of the largest element until k operations are achieved, finally calculating the sum of the remaining stones.