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.
1function minStoneSum(piles, k) {
2 const maxHeap = new MaxPriorityQueue();
3 piles.forEach(pile => maxHeap.enqueue(pile));
4
5 for (let i = 0; i < k; i++) {
6 let largest = maxHeap.dequeue().element;
7 let reduced = largest - Math.floor(largest / 2);
8 maxHeap.enqueue(reduced);
9 }
10
11 let totalStones = 0;
12 maxHeap.toArray().forEach(item => totalStones += item.element);
13 return totalStones;
14}
15
16// Example usage:
17console.log(minStoneSum([5, 4, 9], 2)); // Output: 12
18console.log(minStoneSum([4, 3, 6, 7], 3)); // Output: 12The JavaScript solution leverages a library or custom implementation of a max-heap. It efficiently processes the largest pile for k iterations and returns the sum of the remaining stones using the MaxPriorityQueue.
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.