PIck Maximum Gifts (return sq rt every time)

XXX. Pick Maximum Gifts

Heap

Math

Problem Statement:

Given an array of gift piles and an integer k, you can pick the maximum pile k times. Each time you pick a pile, you take the square root of the pile size and put the floor value back. Return the sum of all piles after k operations.

• Can pick same pile multiple times
• Need floor of square root
• Return final sum of all piles

Java Solution:

public long pickGifts(int[] gifts, int k) {
    // Initialize max heap using lambda comparator
    PriorityQueue giftsHeap = new PriorityQueue<>((a, b) -> 
        Integer.compare(b, a));
    
    // Add all gifts to heap
    for (int gift : gifts) 
        giftsHeap.offer(gift);
    
    // Process for k iterations
    for (int i = 0; i < k; i++) {
        // Get max element and replace with sqrt
        int maxElement = giftsHeap.poll();
        giftsHeap.offer((int)Math.sqrt(maxElement));
    }
    
    // Calculate final sum
    long numberOfRemainingGifts = 0;
    while (!giftsHeap.isEmpty()) 
        numberOfRemainingGifts += giftsHeap.poll();
    
    return numberOfRemainingGifts;
}

Example:

For gifts = [25,64,9,4], k = 4:

• Iteration 1: [64 → 8, 25, 9, 4]
• Iteration 2: [25 → 5, 9, 8, 4]
• Iteration 3: [9 → 3, 8, 5, 4]
• Iteration 4: [8 → 2, 5, 4, 3]
• Final sum = 14

Complexity:

Time Complexity: O(N log N + K log N), where N is array length
Space Complexity: O(N) for heap storage

Implementation Notes:

• **Heap Usage**:
  • Max heap ensures we always process largest pile
  • Custom comparator for max heap behavior
  • Efficient retrieval of maximum element
• **Math Operations**:
  • Use Math.sqrt for square root
  • Cast to int for floor value
  • Use long for final sum to handle large numbers