Remove Stones to Minimize the Total

Problem statement

You have piles of stones given by piles[i]. In one operation you pick any pile and remove floor(pile / 2) stones from it (leave ceil(pile / 2), or equivalently pile - pile/2 in integer math). Perform exactly k such operations and return the minimum possible total number of stones remaining.

Example:

Input:

piles = [5, 4, 9], k = 2

Expected output:

12

Why: one optimal sequence is reduce 9 → 5, then 5 → 3, leaving [5, 4, 3] for a sum of 12.

Practice on LeetCode: Remove Stones to Minimize the Total

Golang Solution

Greedy: always operate on the current largest pile. Keep piles in a max-heap, k times pop the top, replace it with x - x/2, push back, then sum what’s left.

Time: O((n + k) log n)
Space: O(n) for the heap

import "container/heap"

func minStoneSum(piles []int, k int) int {
	h := &maxHeap{}

	for _, pile := range piles {
		heap.Push(h, pile)
	}

	for k > 0 {
		popped := heap.Pop(h).(int)

		popped = popped - popped/2

		heap.Push(h, popped)
		k--
	}

	sum := 0
	for h.Len() > 0 {
		sum += heap.Pop(h).(int)
	}

	return sum
}

type maxHeap []int

func (h maxHeap) Less(i, j int) bool {
	return h[i] > h[j]
}

func (h maxHeap) Len() int {
	return len(h)
}

func (h maxHeap) Swap(i, j int) {
	h[i], h[j] = h[j], h[i]
}

func (h *maxHeap) Push(x any) {
	*h = append(*h, x.(int))
}

func (h *maxHeap) Pop() any {
	old := *h
	n := len(old)
	popped := old[n-1]
	*h = old[:n-1]
	return popped
}