##### Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/2558.html

# 2558. Take Gifts From the Richest Pile

## Description

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.
• Leave behind the floor of the square root of the number of gifts in the pile. Take the rest of the gifts.

Return the number of gifts remaining after k seconds.

Example 1:

Input: gifts = [25,64,9,4,100], k = 4
Output: 29
Explanation:
The gifts are taken in the following way:
- In the first second, the last pile is chosen and 10 gifts are left behind.
- Then the second pile is chosen and 8 gifts are left behind.
- After that the first pile is chosen and 5 gifts are left behind.
- Finally, the last pile is chosen again and 3 gifts are left behind.
The final remaining gifts are [5,8,9,4,3], so the total number of gifts remaining is 29.


Example 2:

Input: gifts = [1,1,1,1], k = 4
Output: 4
Explanation:
In this case, regardless which pile you choose, you have to leave behind 1 gift in each pile.
That is, you can't take any pile with you.
So, the total gifts remaining are 4.


Constraints:

• 1 <= gifts.length <= 103
• 1 <= gifts[i] <= 109
• 1 <= k <= 103

## Solutions

• class Solution {
PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> b - a);
for (int v : gifts) {
pq.offer(v);
}
while (k-- > 0) {
pq.offer((int) Math.sqrt(pq.poll()));
}
long ans = 0;
for (int v : pq) {
ans += v;
}
return ans;
}
}

• class Solution {
public:
while (k--) {
}
}
};

• class Solution:
h = [-v for v in gifts]
heapify(h)
for _ in range(k):
heapreplace(h, -int(sqrt(-h[0])))
return -sum(h)


• func pickGifts(gifts []int, k int) (ans int64) {
heap.Init(h)
for ; k > 0; k-- {
heap.Fix(h, 0)
}
for _, x := range gifts {
ans += int64(x)
}
return
}

type hp struct{ sort.IntSlice }

func (h hp) Less(i, j int) bool { return h.IntSlice[i] > h.IntSlice[j] }
func (hp) Pop() (_ interface{}) { return }
func (hp) Push(interface{})     {}

• impl Solution {
let mut ans = 0;

for _ in 0..k {
if let Some(mut max_gift) = h.pop() {
}
}

for x in h {
ans += x as i64;
}

ans
}
}

• function pickGifts(gifts: number[], k: number): number {
const pq = new MaxPriorityQueue();
for (const v of gifts) {
pq.enqueue(v, v);
}
while (k--) {
let v = pq.dequeue().element;
v = Math.floor(Math.sqrt(v));
pq.enqueue(v, v);
}
let ans = 0;
while (!pq.isEmpty()) {
ans += pq.dequeue().element;
}
return ans;
}