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).
1#include <stdio.h>
2#include <stdlib.h>
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.