2558. Take Gifts From the Richest Pile

Take Gifts From the Richest Pile (LeetCode 2558) is a Easy Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Heap (Priority Queue) Patterns pattern, in the Top K Elements (Selection/Frequency) subpattern.

How to solve Take Gifts From the Richest Pile

Take Gifts From the Richest Pile is a Top K Elements problem, part of Heap (Priority Queue) Patterns. Find top K elements using heap. Solve kth largest, top K frequent, and k closest points problems.

Work towards the solution in these steps:

1. How can you keep track of the largest gifts in the array
2. What is an efficient way to find the square root of a number?
3. Can you keep adding up the values of the gifts while ensuring they are in a certain order?

The reference solution runs in O(k log n + n) time and O(n) space.

The Take Gifts From the Richest Pile solution and editorial walks through the full approach with reference code.

Problem statement

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

Topics and companies

Topics: Array, Heap (Priority Queue), Simulation.

How to practise Take Gifts From the Richest Pile on Thita.ai

Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(k log n + n) time and O(n) space.

Open Take Gifts From the Richest Pile in the code editor, or read the Take Gifts From the Richest Pile editorial for a worked solution with its approach and complexity analysis.

Where Take Gifts From the Richest Pile sits in the DSA pattern sheet

• Heap (Priority Queue) Patterns pattern guide
• Top K Elements (Selection/Frequency) subpattern
• The full DSA patterns sheet

Problems related to Take Gifts From the Richest Pile

Other problems that use the same Top K Elements (Selection/Frequency) and Heap (Priority Queue) Patterns techniques:

• K Closest Points to Origin — Medium, same subpattern
• Kth Largest Element in an Array — Medium, same subpattern
• Kth Largest Element in a Stream — Easy, same subpattern
• Last Stone Weight — Easy, same subpattern
• Relative Ranks — Easy, same subpattern
• Sort Characters By Frequency — Medium, same subpattern

Take Gifts From the Richest Pile FAQ