Problem

You are given a 0-indexed integer array piles, where piles[i] represents the number of stones in the ith pile, and an integer k. You should apply the following operation exactly k times:

  • Choose any piles[i] and remove floor(piles[i] / 2) stones from it.

Notice that you can apply the operation on the same pile more than once.

Return the minimum possible total number of stones remaining after applying the k operations.

floor(x) is the greatest integer that is smaller than or equal to x (i.e., rounds x down).

Examples

Example 1:

1
2
3
4
5
6
7
8

Input:
piles = [5,4,9], k = 2
Output:
 12
Explanation: Steps of a possible scenario are:
- Apply the operation on pile 2. The resulting piles are [5,4,5].
- Apply the operation on pile 0. The resulting piles are [3,4,5].
The total number of stones in [3,4,5] is 12.

Example 2:

1
2
3
4
5
6
7
8
9

Input:
piles = [4,3,6,7], k = 3
Output:
 12
Explanation: Steps of a possible scenario are:
- Apply the operation on pile 2. The resulting piles are [4,3,3,7].
- Apply the operation on pile 3. The resulting piles are [4,3,3,4].
- Apply the operation on pile 0. The resulting piles are [2,3,3,4].
The total number of stones in [2,3,3,4] is 12.

Solution

Method 1 – Greedy with Max Heap

Intuition

To minimize the total number of stones, we should always remove stones from the largest pile, as this reduces the total the most in each operation. Using a max heap allows us to efficiently select and update the largest pile at each step.

Approach

  1. Insert all piles into a max heap (priority queue).
  2. For k times:
    • Pop the largest pile.
    • Remove floor(pile / 2) stones (i.e., update pile to pile - floor(pile / 2) or equivalently ceil(pile / 2)).
    • Push the updated pile back into the heap.
  3. After all operations, sum the remaining stones in the heap and return the result.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
public:
    int minStoneSum(vector<int>& piles, int k) {
        priority_queue<int> pq(piles.begin(), piles.end());
        while (k--) {
            int x = pq.top(); pq.pop();
            x -= x / 2;
            pq.push(x);
        }
        int ans = 0;
        while (!pq.empty()) {
            ans += pq.top(); pq.pop();
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

func minStoneSum(piles []int, k int) int {
    h := &IntHeap{}
    heap.Init(h)
    for _, v := range piles {
        heap.Push(h, -v)
    }
    for i := 0; i < k; i++ {
        x := -heap.Pop(h).(int)
        x -= x / 2
        heap.Push(h, -x)
    }
    ans := 0
    for h.Len() > 0 {
        ans += -heap.Pop(h).(int)
    }
    return ans
}
// type IntHeap and heap interface methods omitted for brevity
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
    public int minStoneSum(int[] piles, int k) {
        PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
        for (int p : piles) pq.add(p);
        while (k-- > 0) {
            int x = pq.poll();
            pq.add(x - x / 2);
        }
        int ans = 0;
        while (!pq.isEmpty()) ans += pq.poll();
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
    fun minStoneSum(piles: IntArray, k: Int): Int {
        val pq = PriorityQueue<Int>(compareByDescending { it })
        for (p in piles) pq.add(p)
        repeat(k) {
            val x = pq.poll()
            pq.add(x - x / 2)
        }
        return pq.sum()
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

import heapq
class Solution:
    def minStoneSum(self, piles: list[int], k: int) -> int:
        h = [-x for x in piles]
        heapq.heapify(h)
        for _ in range(k):
            x = -heapq.heappop(h)
            x -= x // 2
            heapq.heappush(h, -x)
        return -sum(h)
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

impl Solution {
    pub fn min_stone_sum(piles: Vec<i32>, k: i32) -> i32 {
        use std::collections::BinaryHeap;
        let mut pq = BinaryHeap::from(piles);
        for _ in 0..k {
            let mut x = pq.pop().unwrap();
            x -= x / 2;
            pq.push(x);
        }
        pq.iter().sum()
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
    minStoneSum(piles: number[], k: number): number {
        const h = new MaxPriorityQueue<number>({priority: x => x});
        for (const p of piles) h.enqueue(p);
        for (let i = 0; i < k; i++) {
            let x = h.dequeue().element;
            x -= Math.floor(x / 2);
            h.enqueue(x);
        }
        let ans = 0;
        while (!h.isEmpty()) ans += h.dequeue().element;
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(k log n), where n is the number of piles. Each operation on the heap is O(log n) and we do k operations.
  • 🧺 Space complexity: O(n), for the heap.