Shrinking Treasure Piles
Problem
A dragon guards several piles of gold coins, piles[i] coins each. Every night, for k nights, a thief sneaks in, picks the pile with the most coins and takes from it until only floor(sqrt(x)) coins remain, where x is that pile's size. If several piles are tied for largest, any of them may be picked; the result is the same.
Return the total number of coins left in all piles after k nights.
Example 1
- Input:
- piles = [30, 9, 100], k = 2
- Output:
- 24
Night 1: 100 → 10, piles [30, 9, 10]. Night 2: 30 → 5, piles [5, 9, 10]. Total 24.
Example 2
- Input:
- piles = [1, 1, 1], k = 5
- Output:
- 3
floor(sqrt(1)) = 1, so nothing changes.
Example 3
- Input:
- piles = [64], k = 3
- Output:
- 1
64 → 8 → 2 → 1.
Constraints
- 1 ≤ piles.length ≤ 10^4
- 1 ≤ piles[i] ≤ 10^9
- 1 ≤ k ≤ 10^4
Hint
Show the first hint
Each night you need the current largest pile, and one pile changes.
Walkthrough
How to approach it
01Clarify before coding
- Does a tie between largest piles change the answer? No: equal piles produce equal results.
- Is the square root floored? Yes, integer square root.
- Can k exceed the number of piles? Yes; a pile can be picked many times.
02Brute force
Each night scan all piles for the maximum and shrink it.
Cost: O(k · n) = 10^8 for the limits: borderline in Python and wasteful, since only one pile changes per night.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.