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).
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.