We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Take Gifts From the Richest Pile

Number: 2692

Difficulty: Easy

Paid? No

Companies: Google, Amazon, DE Shaw

Problem Description

Given an array gifts representing the number of gifts in several piles, every second choose the pile with the maximum number of gifts and reduce its count to the floor of its square root. After k seconds, return the total number of gifts remaining.

Key Insights

  • Use a max-heap (priority queue) to quickly access the pile with the maximum gifts.
  • Since some languages (like Python) provide a min-heap by default, store negative values to simulate a max-heap.
  • Each iteration reduces the largest pile using floor(sqrt(value)).
  • Simulation runs for k iterations, updating the heap at each step.

Space and Time Complexity

Time Complexity: O(k log n) where n is the number of piles. Space Complexity: O(n) for maintaining the heap.

Solution

We use a max-heap to store the gifts. For each of the k seconds, we pop the largest element, compute its new value using the floor of its square root, and push it back into the heap. Finally, we sum all the elements in the heap to produce the result.

Code Solutions

import heapq
import math

def pickGifts(gifts, k):
    # Initialize a max-heap using negative values
    max_heap = [-gift for gift in gifts]
    heapq.heapify(max_heap)
    
    for _ in range(k):
        # Pop the largest element (negated to get actual value)
        current = -heapq.heappop(max_heap)
        # Compute new value as floor of square root
        new_gift = int(math.sqrt(current))
        # Push the updated value back into the heap (negated)
        heapq.heappush(max_heap, -new_gift)
        
    # Calculate the total gifts remaining (negate again to get real values)
    return -sum(max_heap)

# Example usage:
print(pickGifts([25, 64, 9, 4, 100], 4))
← Back to All Questions