Take Gifts From the Richest Pile

2558. Take Gifts From the Richest Pile

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:

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?
4. 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:

1. 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.

2. 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.

3. 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
?>




<h3>
  
  
  Explanation:
</h3>

<ol>
<li>
<p><strong>Heap Initialization</strong>:</p>

<ul>
<li>
SplPriorityQueue is used to simulate a max-heap. The insert method allows us to push elements into the heap with a priority.</li>
</ul>
</li>
<li>
<p><strong>Processing the Largest Pile</strong>:</p>

<ul>
<li>For k iterations, the largest pile is extracted using extract.</li>
<li>The number of gifts left behind is calculated as the floor of the square root of the current largest pile using floor(sqrt(...)).</li>
<li>The reduced pile is re-inserted into the heap.</li>
</ul>
</li>
<li>
<p><strong>Summing Remaining Gifts</strong>:</p>

<ul>
<li>After the k operations, all elements in the heap are extracted and summed up to get the total number of remaining gifts.</li>
</ul>
</li>
<li>
<p><strong>Edge Cases</strong>:</p>

<ul>
<li>If gifts is empty, the result is 0.</li>
<li>If k is larger than the number of operations possible, the algorithm gracefully handles it.</li>
</ul>
</li>
</ol>

<h3>
  
  
  Time Complexity:
</h3>

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

<p>Thus, the total time complexity is <em><strong>O(k log n)</strong></em>, where <em><strong>n</strong></em> is the number of piles and <em><strong>k</strong></em> is the number of seconds.</p>

<h3>
  
  
  Example Walkthrough:
</h3>

<p>For the input:<br>
</p>
<pre class="brush:php;toolbar:false"><?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
?>

1. Initially, the priority queue has the piles: [25, 64, 9, 4, 100].
2. After 1 second: Choose 100, leave 10 behind. The remaining gifts are: [25, 64, 9, 4, 10].
3. After 2 seconds: Choose 64, leave 8 behind. The remaining gifts are: [25, 8, 9, 4, 10].
4. After 3 seconds: Choose 25, leave 5 behind. The remaining gifts are: [5, 8, 9, 4, 10].
5. 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!

If you want more helpful content like this, feel free to follow me:

• LinkedIn
• GitHub

The above is the detailed content of Take Gifts From the Richest Pile. For more information, please follow other related articles on the PHP Chinese website!