Take Gifts From the Richest Pile

Difficulty: Easy | Acceptance: 75.50% | Paid: No 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 are multiple piles 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.

• Examples
• Constraints
• Max Heap (Priority Queue)
• Simulation with Sorting
• Linear Search (Naive)

Examples

Input: gifts = [25,64,9,4,100], k = 4
Output: 29
Explanation: 
The seconds are as follows:
- In the first second, the pile with the most gifts is 100. We take 100 leaving floor(sqrt(100)) = 10 gifts. The array becomes [25,64,9,4,10].
- In the second second, the pile with the most gifts is 64. We take 64 leaving floor(sqrt(64)) = 8 gifts. The array becomes [25,8,9,4,10].
- In the third second, the pile with the most gifts is 25. We take 25 leaving floor(sqrt(25)) = 5 gifts. The array becomes [5,8,9,4,10].
- In the fourth second, the pile with the most gifts is 10. We take 10 leaving floor(sqrt(10)) = 3 gifts. The array becomes [5,8,9,4,3].
The total number of gifts remaining is 5 + 8 + 9 + 4 + 3 = 29.

Input: gifts = [1,1,1,1], k = 4
Output: 0
Explanation: 
In each second, we choose the pile with the most gifts which is 1. We take 1 leaving floor(sqrt(1)) = 0 gifts. The array becomes [0,0,0,0] after 4 seconds.

Constraints

- 1 <= gifts.length <= 10^3
- 1 <= gifts[i] <= 10^9
- 1 <= k <= 10^3

Max Heap (Priority Queue)

Intuition We need to repeatedly access the maximum element in the array. A Max Heap (Priority Queue) is the ideal data structure for this, as it allows us to extract the maximum element and insert a new element in logarithmic time.

Steps

• Initialize a Max Heap with all elements from the gifts array.
• Loop k times:
  • Extract the maximum element from the heap.
  • Calculate the number of gifts to leave behind: floor(sqrt(max)).
  • Push the remaining gifts back into the heap.
• Sum all elements remaining in the heap and return the result.

import heapq
import math
from typing import List

class Solution:
    def pickGifts(self, gifts: List[int], k: int) -> int:
        # Python's heapq is a min-heap, so we invert values to simulate a max-heap
        max_heap = [-g for g in gifts]
        heapq.heapify(max_heap)
        
        for _ in range(k):
            if not max_heap:
                break
            # Get the largest value (remember to invert back)
            current = -heapq.heappop(max_heap)
            remaining = int(math.sqrt(current))
            # Push the remaining back (invert again)
            heapq.heappush(max_heap, -remaining)
            
        # Sum the remaining gifts (invert back)
        return sum(-x for x in max_heap)

Complexity

• Time: O(n + k log n), where n is the number of piles. Building the heap takes O(n), and we perform k operations of O(log n) each.
• Space: O(n) to store the heap.
• Notes: This is the most efficient approach for larger input sizes.

Simulation with Sorting

Intuition Since the constraints are small (n and k up to 10³), we can afford to sort the array in every iteration to find the maximum element. This avoids the overhead of a heap data structure.

Steps

• Loop k times:
  • Sort the array in descending order.
  • Update the first element (the largest) to be floor(sqrt(first_element)).
• Return the sum of the array.

import math
from typing import List

class Solution:
    def pickGifts(self, gifts: List[int], k: int) -> int:
        for _ in range(k):
            # Sort in descending order
            gifts.sort(reverse=True)
            # Update the largest pile
            gifts[0] = int(math.sqrt(gifts[0]))
        return sum(gifts)

Complexity

• Time: O(k * n log n), where n is the number of piles. We sort n elements k times.
• Space: O(1) or O(n) depending on the sorting algorithm’s space complexity.
• Notes: Simpler to implement than a heap, but slower for large inputs.

Linear Search (Naive)

Intuition We can simply scan the array to find the maximum element in every iteration. This avoids sorting but requires O(n) time per iteration to find the max.

Steps

• Loop k times:
  • Find the index of the maximum element in the array.
  • Update the value at that index to floor(sqrt(value)).
• Return the sum of the array.

import math
from typing import List

class Solution:
    def pickGifts(self, gifts: List[int], k: int) -> int:
        for _ in range(k):
            max_idx = 0
            # Find index of max element
            for i in range(len(gifts)):
                if gifts[i] > gifts[max_idx]:
                    max_idx = i
            # Update max element
            gifts[max_idx] = int(math.sqrt(gifts[max_idx]))
        return sum(gifts)

Complexity

• Time: O(k * n), where n is the number of piles. We perform a linear scan k times.
• Space: O(1), no extra space used.
• Notes: This is often faster than sorting for small k, but slower than the heap approach for larger inputs.