2558. Take Gifts From the Richest Pile

#php #leetcode #algorithms #programming

Difficulty: Easy

Topics: Array, Heap (Priority Queue), Simulation

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 <= 10³
1 <= gifts[i] <= 10⁹
1 <= k <= 10³

Hint:

How can you keep track of the largest gifts in the array
What is an efficient way to find the square root of a number?
Can you keep adding up the values of the gifts while ensuring they are in a certain order?
Can we use a priority queue or heap here?

Solution:

We can utilize a max-heap (priority queue) since we need to repeatedly pick the pile with the maximum number of gifts. A max-heap will allow us to efficiently access the largest pile in constant time and update the heap after taking gifts from the pile.

Approach:

Use a Max-Heap:
- Since we need to repeatedly get the pile with the maximum number of gifts, a max-heap (priority queue) is ideal. In PHP, we can use SplPriorityQueue, which is a priority queue that by default works as a max-heap.
- To simulate a max-heap, we will insert the number of gifts as a negative value, since SplPriorityQueue is a min-heap by default. By inserting negative values, the smallest negative value will represent the largest original number.
Process Each Second:
- In each second, pop the pile with the maximum number of gifts from the heap.
- Take all the gifts except the floor of the square root of the number of gifts in that pile.
- Push the modified pile back into the heap.
Termination:
- We stop after k seconds or once we've processed all the seconds.

Let's implement this solution in PHP: 2558. Take Gifts From the Richest Pile

<?php
/**
 * @param Integer[] $gifts
 * @param Integer $k
 * @return Integer
 */
function pickGifts($gifts, $k) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example usage:
$gifts1 = [25, 64, 9, 4, 100];
$k1 = 4;
echo pickGifts($gifts1, $k1) . "\n"; // Output: 29

$gifts2 = [1, 1, 1, 1];
$k2 = 4;
echo pickGifts($gifts2, $k2) . "\n"; // Output: 4
?>

Explanation:

Heap Initialization:
- SplPriorityQueue is used to simulate a max-heap. The insert method allows us to push elements into the heap with a priority.
Processing the Largest Pile:
- For k iterations, the largest pile is extracted using extract.
- The number of gifts left behind is calculated as the floor of the square root of the current largest pile using floor(sqrt(...)).
- The reduced pile is re-inserted into the heap.
Summing Remaining Gifts:
- After the k operations, all elements in the heap are extracted and summed up to get the total number of remaining gifts.
Edge Cases:
- If gifts is empty, the result is 0.
- If k is larger than the number of operations possible, the algorithm gracefully handles it.

Time Complexity:

Heap operations (insert and extract): Each heap operation (insertion and extraction) takes O(log n), where n is the number of piles.
Looping through k operations: We perform k operations, each involving heap extraction and insertion, both taking O(log n).

Thus, the total time complexity is O(k log n), where n is the number of piles and k is the number of seconds.

Example Walkthrough:

For the input:

$gifts = [25, 64, 9, 4, 100];
$k = 4;

Initially, the priority queue has the piles: [25, 64, 9, 4, 100].
After 1 second: Choose 100, leave 10 behind. The remaining gifts are: [25, 64, 9, 4, 10].
After 2 seconds: Choose 64, leave 8 behind. The remaining gifts are: [25, 8, 9, 4, 10].
After 3 seconds: Choose 25, leave 5 behind. The remaining gifts are: [5, 8, 9, 4, 10].
After 4 seconds: Choose 10, leave 3 behind. The remaining gifts are: [5, 8, 9, 4, 3].

The sum of the remaining gifts is 5 + 8 + 9 + 4 + 3 = 29.

This approach efficiently solves the problem using a max-heap and performs well within the given constraints.

Contact Links

If you found this series helpful, please consider giving the repository a star on GitHub or sharing the post on your favorite social networks 😍. Your support would mean a lot to me!