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 java.util.PriorityQueue;
2
3public class StoneRemoval {
4 public int minStoneSum(int[] piles, int k) {
5 PriorityQueue<Integer> maxHeap = new PriorityQueue<>( (a, b) -> b - a );
6 for (int pile : piles) {
7 maxHeap.add(pile);
8 }
9
10 for (int i = 0; i < k; i++) {
11 int largest = maxHeap.poll();
12 int reduced = largest - largest / 2;
13 maxHeap.add(reduced);
14 }
15
16 int totalStones = 0;
17 while (!maxHeap.isEmpty()) {
18 totalStones += maxHeap.poll();
19 }
20 return totalStones;
21 }
22
23 // Example usage
24 public static void main(String[] args) {
25 StoneRemoval sr = new StoneRemoval();
26 System.out.println(sr.minStoneSum(new int[]{5, 4, 9}, 2)); // Output: 12
27 System.out.println(sr.minStoneSum(new int[]{4, 3, 6, 7}, 3)); // Output: 12
28 }
29}The Java solution uses a PriorityQueue to implement a max-heap with a custom comparator. Each iteration reduces the largest pile and adds it back to the heap. Finally, it calculates the total of remaining stones.
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.