Remove stones to minimize the total

Array Greedy Heap (Priority Queue)

65.5% acceptance

Feb 25, 2026

1960

182

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 largest integer that is smaller than or equal to x (i.e., rounds x down).

Solution

Rust

Time O(n log n)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn min_stone_sum(piles: Vec<i32>, k: i32) -> i32 {
    use std::collections::BinaryHeap;
    let mut heap: BinaryHeap<i32> = piles.into_iter().collect();
    for _ in 0..k {
      if let Some(top) = heap.pop() {
        heap.push(top - top / 2);
      }
    }
    heap.into_iter().sum()
  }
}