# 12.12.2024 [2558. Take Gifts From the Richest Pile]

Sum after `k-Sqrt` of tops in array #easy

12.12.2024

2558. Take Gifts From the Richest Pile medium blog post substack youtube deep-dive

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/830

Problem TLDR

Sum after k-Sqrt of tops in array #easy

Intuition

We can use a heap.

Approach

• some extra attention should be paid to use an sqrt: in Kotiln & Rust convert to Double, in Rust we aren't able to sort Doubles, so convert back.

• c++ is much more forgiving

Complexity

• Time complexity: $$O(nlog(n))$$

• Space complexity: $$O(n)$$

Code

    fun pickGifts(gifts: IntArray, k: Int): Long {
        val pq = PriorityQueue(gifts.map { -it.toDouble() }) 
        for (i in 1..k) pq += -floor(sqrt(-pq.poll()))
        return -pq.sum().toLong()
    }

    pub fn pick_gifts(gifts: Vec<i32>, k: i32) -> i64 {
        let mut bh = BinaryHeap::from_iter(gifts);
        for i in 0..k {
            let x = bh.pop().unwrap();
            bh.push(((x as f64).sqrt()).floor() as i32)
        }
        bh.iter().map(|&x| x as i64).sum()
    }

    long long pickGifts(vector<int>& gifts, int k) {
        priority_queue<int> pq; long long res = 0;
        for (int g: gifts) pq.push(g);
        while (k--) {
            int x = pq.top(); pq.pop();
            pq.push(sqrt(x));
        }
        while (pq.size()) res += pq.top(), pq.pop();
        return res;
    }