Minimum Health to Beat Game
Real-world version: Least Charge to Get Through the RoundsThe statement here is our own: the same inputs, outputs and technique.
A machine runs through rounds in order, and round i drains damage[i] charge.
The machine carries one shield of strength armor, which may be used on at most one round. Used on a round, it absorbs that round's drain up to its own strength, so the drain becomes whatever is left over.
The machine must keep strictly more than zero charge at every moment. Return the least charge it can start with and still get through every round.
Examples
Example 1
- Input
- damage = [14, 3, 27, 9], armor = 12
- Output
- 42
The rounds drain 53 in total. The shield is worth most on the round draining 27, where it absorbs all 12 of its strength, leaving 41 to be paid for and one charge to be kept.
Example 2
- Input
- damage = [1], armor = 5
- Output
- 1
The shield is stronger than the only round, so it absorbs the whole drain and the machine needs only the one charge it must keep.
Example 3
- Input
- damage = [0, 0, 0], armor = 10
- Output
- 1
Nothing drains at all, so the machine needs only the charge it must keep.
Constraints
- 1 <= damage.length <= 10^5
- 0 <= damage[i] <= 10^5
- 0 <= armor <= 10^5
The signature
The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.
def minimum_health(damage: list[int], armor: int) -> int:public long minimumHealth(int[] damage, int armor)Checking your plan…
How this problem was checked
- Passed: Reference solution run against 11 test cases: 11 passed
- Passed: 3 worked examples confirmed by running the code
- Passed: 0 eight-word sequences shared with the parent problem's text
- Passed: Agrees with an independent brute-force solution on random inputs
- Passed: Test set shown to catch deliberately broken solutions
- Passed: Reviewed by a separate quality pass
- Passed: Function arity matches the parent problem's