Remove Stones to Minimize the Total solution and explanation

import heapq

def min_stone_sum(piles, k):
    max_heap = [-pile for pile in piles]  # Use negative values to simulate max-heap
    heapq.heapify(max_heap)
    
    for _ in range(k):
        largest = -heapq.heappop(max_heap)
        reduced = largest - largest // 2
        heapq.heappush(max_heap, -reduced)
    
    return -sum(max_heap)

# Example usage:
print(min_stone_sum([5, 4, 9], 2))  # Output: 12
print(min_stone_sum([4, 3, 6, 7], 3))  # Output: 12

import java.util.PriorityQueue;

public class StoneRemoval {
    public int minStoneSum(int[] piles, int k) {
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>( (a, b) -> b - a );
        for (int pile : piles) {
            maxHeap.add(pile);
        }

        for (int i = 0; i < k; i++) {
            int largest = maxHeap.poll();
            int reduced = largest - largest / 2;
            maxHeap.add(reduced);
        }

        int totalStones = 0;
        while (!maxHeap.isEmpty()) {
            totalStones += maxHeap.poll();
        }
        return totalStones;
    }

    // Example usage
    public static void main(String[] args) {
        StoneRemoval sr = new StoneRemoval();
        System.out.println(sr.minStoneSum(new int[]{5, 4, 9}, 2));  // Output: 12
        System.out.println(sr.minStoneSum(new int[]{4, 3, 6, 7}, 3));  // Output: 12
    }
}

function minStoneSum(piles, k) {
    const maxHeap = new MaxPriorityQueue();  
    piles.forEach(pile => maxHeap.enqueue(pile));
    
    for (let i = 0; i < k; i++) {
        let largest = maxHeap.dequeue().element;
        let reduced = largest - Math.floor(largest / 2);
        maxHeap.enqueue(reduced);
    }
    
    let totalStones = 0;
    maxHeap.toArray().forEach(item => totalStones += item.element);
    return totalStones;
}

// Example usage:
console.log(minStoneSum([5, 4, 9], 2));  // Output: 12
console.log(minStoneSum([4, 3, 6, 7], 3));  // Output: 12

#include <stdio.h>
#include <stdlib.h>

int compare(const void * a, const void * b) {
    return (*(int*)b - *(int*)a);
}

int minStoneSum(int* piles, int pilesSize, int k) {
    while (k--) {
        qsort(piles, pilesSize, sizeof(int), compare);
        piles[0] -= piles[0] / 2;
    }
    int total = 0;
    for (int i = 0; i < pilesSize; i++) {
        total += piles[i];
    }
    return total;
}

int main() {
    int piles1[] = {5, 4, 9};
    printf("%d\n", minStoneSum(piles1, 3, 2));  // Output: 12
    int piles2[] = {4, 3, 6, 7};
    printf("%d\n", minStoneSum(piles2, 4, 3));  // Output: 12
    return 0;
}

using System;
using System.Linq;

public class StoneRemoval {
    public int MinStoneSum(int[] piles, int k) {
        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
    }
}

class Solution {
public:
    int minStoneSum(vector<int>& piles, int k) {
        priority_queue<int> pq;
        for (int x : piles) {
            pq.push(x);
        }
        while (k--) {
            int x = pq.top();
            pq.pop();
            pq.push(x - x / 2);
        }
        int ans = 0;
        while (!pq.empty()) {
            ans += pq.top();
            pq.pop();
        }
        return ans;
    }
};

function minStoneSum(piles: number[], k: number): number {
    const pq = new MaxPriorityQueue<number>();
    for (const x of piles) {
        pq.enqueue(x);
    }
    while (k--) {
        pq.enqueue((pq.dequeue() + 1) >> 1);
    }
    return pq.toArray().reduce((a, b) => a + b, 0);
}

func minStoneSum(piles []int, k int) (ans int) {
	pq := &hp{piles}
	heap.Init(pq)
	for ; k > 0; k-- {
		x := pq.pop()
		pq.push(x - x/2)
	}
	for pq.Len() > 0 {
		ans += pq.pop()
	}
	return
}

type hp struct{ sort.IntSlice }

func (h hp) Less(i, j int) bool { return h.IntSlice[i] > h.IntSlice[j] }
func (h *hp) Push(v any)        { h.IntSlice = append(h.IntSlice, v.(int)) }
func (h *hp) Pop() any {
	a := h.IntSlice
	v := a[len(a)-1]
	h.IntSlice = a[:len(a)-1]
	return v
}
func (h *hp) push(v int) { heap.Push(h, v) }
func (h *hp) pop() int   { return heap.Pop(h).(int) }