2558. Take Gifts From the Richest Pile LeetCode Solution

In this guide, you will get 2558. Take Gifts From the Richest Pile LeetCode Solution with the best time and space complexity. The solution to Take Gifts From the Richest Pile problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Take Gifts From the Richest Pile solution in C++
Take Gifts From the Richest Pile solution in Java
Take Gifts From the Richest Pile solution in Python
Additional Resources

2558. Take Gifts From the Richest Pile LeetCode Solution image

Problem Statement of Take Gifts From the Richest Pile

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.

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

Complexity Analysis

Time Complexity: O(k\log n)
Space Complexity: O(n)

2558. Take Gifts From the Richest Pile LeetCode Solution in C++

class Solution {
 public:
  long long pickGifts(vector<int>& gifts, int k) {
    long ans = 0;
    priority_queue<int> maxHeap;

    for (const int gift : gifts)
      maxHeap.push(gift);

    for (int i = 0; i < k; ++i) {
      const int squaredMax = sqrt(maxHeap.top());
      maxHeap.pop();
      maxHeap.push(squaredMax);
    }

    while (!maxHeap.empty())
      ans += maxHeap.top(), maxHeap.pop();

    return ans;
  }
};
/* code provided by PROGIEZ */

2558. Take Gifts From the Richest Pile LeetCode Solution in Java

class Solution {
  public long pickGifts(int[] gifts, int k) {
    long ans = 0;
    Queue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());

    for (final int gift : gifts)
      maxHeap.offer(gift);

    for (int i = 0; i < k; ++i) {
      final int squaredMax = (int) Math.sqrt(maxHeap.poll());
      maxHeap.offer(squaredMax);
    }

    while (!maxHeap.isEmpty())
      ans += maxHeap.poll();

    return ans;
  }
}
// code provided by PROGIEZ

2558. Take Gifts From the Richest Pile LeetCode Solution in Python

class Solution:
  def pickGifts(self, gifts: list[int], k: int) -> int:
    maxHeap = [-gift for gift in gifts]
    heapq.heapify(maxHeap)

    for _ in range(k):
      squaredMax = math.isqrt(-heapq.heappop(maxHeap))
      heapq.heappush(maxHeap, -squaredMax)

    return -sum(maxHeap)
 # code by PROGIEZ