Reduce largest piles
Repeatedly find the maximum pile and replace it with its integer square root. About 8 minutes.
The gift pile reduction
You are given piles of gifts. Each second, you pick the pile with the most gifts, leave behind the whole-number square root of it, and take the rest. After a set number of seconds, you want to know how many gifts remain in total.
Picture a generous neighbour who keeps raiding the biggest pile in the shop.
- total
- 112
Second 1: the biggest pile is 100. Leave √100 = 10.
Efficiency with a max-heap
Because you only change one pile each second, the other piles stay where they were. Pushing and popping on a max-heap fixes the order in logarithmic time, so you don't re-sort everything each time.
Do this for the given number of seconds, then add up what is left.
import heapq
import math
heap = [-g for g in gifts]
heapq.heapify(heap)
for _ in range(k):
m = -heapq.heappop(heap)
heapq.heappush(heap, -math.isqrt(m))
return -sum(heap)If a pile of 25 gifts is reduced, what does it become?
- A5
- B20
- C12
Show the answer
5. floor(sqrt(25)) = 5.
Reduce largest piles
You are given an integer array gifts denoting the number of gifts in various piles. Every second for k seconds: 1. Choose the pile with the maximum number of gifts. 2. Leave behind floor(sqrt(gifts)) in that pile, taking the rest. Return the total number of gifts remaining across all piles after k seconds.
gifts = [25, 64, 9, 4, 100], k = 4 → 29
1 ≤ gifts.length ≤ 100,000 · 1 ≤ gifts[i] ≤ 1,000,000,000 · 1 ≤ k ≤ 100,000