570. Halve the Piles
A warehouse stores crates in n stacks, where piles[i] is the number of crates in stack i. A clearing operation chooses one stack with x crates and removes exactly floor(x / 2) of them, leaving x - floor(x / 2) crates (the larger half, rounded up).
You must perform exactly k clearing operations. A stack may be chosen repeatedly, and choosing a stack with a single crate removes nothing but is still allowed. Return the smallest possible total number of crates left across all stacks after the k operations.
The answer always fits in a 32-bit signed integer. Aim for O((n + k) log n) time and O(n) space.
Example 1
- Input:
- piles = [9,4,7], k = 2
- Output:
- 13
- Explanation:
Clear 9 (leaves 5, removes 4) and then 7 (leaves 4, removes 3), giving [5,4,4] with total 13.
Example 2
- Input:
- piles = [10], k = 3
- Output:
- 2
- Explanation:
The single stack goes 10, 5, 3, 2, so 2 crates remain.
Example 3
- Input:
- piles = [1,1], k = 5
- Output:
- 2
- Explanation:
A stack of one crate loses nothing, so the total stays 2.
Constraints
1 ≤ piles.length ≤ 1000001 ≤ piles[i] ≤ 1041 ≤ k ≤ 100000
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 2,000 msC++ 500 msJava 1,000 msJavaScript 1,000 msTypeScript 1,000 ms
Expected complexity
- Time
- O((n + k) log n)
- Space
- O(n)