LeetCode Entry
2558. Take Gifts From the Richest Pile
Sum after k-Sqrt of tops in array
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;
}