Take gifts from the richest pile

Array Heap (Priority Queue) Simulation

75.5% acceptance

Feb 25, 2026

847

You are given an integer array gifts denoting the number of gifts in various piles. Every second, you do the following: Choose the pile with the maximum number of gifts. If there is more than one pile with the maximum number of gifts, choose any. Reduce the number of gifts in the pile to the floor of the square root of the original number of gifts in the pile. Return the number of gifts remaining after k seconds.

Solution

Rust

Time O(n log n)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn pick_gifts(gifts: Vec<i32>, k: i32) -> i64 {
    use std::collections::BinaryHeap;
    let mut heap: BinaryHeap<i32> = gifts.into_iter().collect();
    for _ in 0..k {
      if let Some(max) = heap.pop() {
        let new_val = (max as f64).sqrt() as i32;
        heap.push(new_val);
      }
    }
    heap.iter().map(|&x| x as i64).sum()
  }
}