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 = 4Output
29The 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 = 4Output
4Every chosen pile still leaves behind 1 gift, so the total number of gifts remaining is 4.
Constraints
- 1 <= gifts.length <= 10^3
- 1 <= gifts[i] <= 10^9
- 1 <= k <= 10^3