Minimum Health to Beat Game
- 1 min read
- Array
- LC-Medium
3 years ago
Solution
- The most efficient use of armor here is to use it on the damage index where damage is the highest
- So first find the index with the highest damage, and update it with new damage by subtracting it with armor
- Remember that if it's goes negative, set it back to 0 since you can take 0 damage, it doesn't make sense if you can take negative damage
- After this, just return
sum(damage) + 1because unlike Koko Eating Bananas, the calculations is very very straightforward
| Time | Space | Explanation |
|---|---|---|
O() | O() |
def minimumHealth(self, damage: List[int], armor: int) -> int:
highest_damage = max(damage)
highest_damage_idx = damage.index(highest_damage)
damage[highest_damage_idx] = max(0, damage[highest_damage_idx] - armor)
return sum(damage) + 1