2558. Take Gifts From the Richest Pile

EasyView on LeetCode

Array Greedy Heap (Priority Queue)Simulation

Time: O(n + k log n)

Space: O(n)

Problem Overview

Repeat k times: take the largest pile, replace it with floor(sqrt(value)).

Intuition

Repeat k times: take the largest pile, replace it with floor(sqrt(value)). Use a max-heap to fetch the maximum in O(log n) each round. After k operations, sum everything left in the heap.

Algorithm

1Push all gifts into a max-priority queue.
2Repeat k times: pop max, push (int)Math.Floor(Math.Sqrt(max)).
3Drain heap and sum remaining values (use long for sum).
4Return total.

Example Walkthrough

Input: gifts = [25,64,9], k = 2

1.Pop 64 → push 8. Pop 25 → push 5.
2.Remaining piles 9, 8, 5 → sum 22.

Output: 22

Common Pitfalls

•Use floor of square root, not round.
•Sum can exceed int — accumulate in long.
•k operations, not until heap empty.

2558.cs

// Approach: Max-heap; k times take max and push floor(sqrt(max)) back.
// Time: O(n + k log n) Space: O(n)

public class Solution
{
    public long PickGifts(int[] gifts, int k)
    {
        long ans = 0;
        PriorityQueue<int, int> maxHeap = new PriorityQueue<int, int>();

        foreach (int gift in gifts)
            maxHeap.Enqueue(gift, -gift); // Use negative priority for max-heap behavior

        for (int i = 0; i < k; ++i)
        {
            int maxGift = maxHeap.Dequeue();
            int squaredMax = (int)Math.Sqrt(maxGift);
            maxHeap.Enqueue(squaredMax, -squaredMax);
        }

        while (maxHeap.TryDequeue(out int result, out int _))
            ans += result;

        return ans;
    }
}

Was this solution helpful?