#2558
Take Gifts From the Richest Pile
newbie · 230 · lc easy +17 · verified · 75.5% accepted · 849 likes · top 86%
Description
Given an integer array gifts representing the sizes of gift piles, each second you select the largest pile and replace its count with the floor of its square root. After k seconds, return the total number of gifts remaining across all piles.
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.
Code
1
2
3