Minimum Health to Beat Game

Problem Statement

In this scenario, a player is navigating through n levels of a game, each level causing a certain amount of health damage to the player. The amount of damage taken at each level is represented by the damage[] array where damage[i] denotes the health lost at level i. To aid in surviving the game, the player is equipped with armor that can be deployed once to mitigate up to armor amount of damage at any chosen level. To successfully complete the game, the player's health must always remain above zero.

The challenge lies in determining the minimum starting health needed for the player to survive through all levels with the strategic use of the armor.

Examples

Example 1

Input:

damage = [2,7,4,3], armor = 4

Output:

13

Explanation:

One optimal way to beat the game starting at 13 health is:
On round 1, take 2 damage. You have 13 - 2 = 11 health.
On round 2, take 7 damage. You have 11 - 7 = 4 health.
On round 3, use your armor to protect you from 4 damage. You have 4 - 0 = 4 health.
On round 4, take 3 damage. You have 4 - 3 = 1 health.
Note that 13 is the minimum health you need to start with to beat the game.

Example 2

Input:

damage = [2,5,3,4], armor = 7

Output:

10

Explanation:

One optimal way to beat the game starting at 10 health is:
On round 1, take 2 damage. You have 10 - 2 = 8 health.
On round 2, use your armor to protect you from 5 damage. You have 8 - 0 = 8 health.
On round 3, take 3 damage. You have 8 - 3 = 5 health.
On round 4, take 4 damage. You have 5 - 4 = 1 health.
Note that 10 is the minimum health you need to start with to beat the game.

Example 3

Input:

damage = [3,3,3], armor = 0

Output:

10

Explanation:

One optimal way to beat the game starting at 10 health is:
On round 1, take 3 damage. You have 10 - 3 = 7 health.
On round 2, take 3 damage. You have 7 - 3 = 4 health.
On round 3, take 3 damage. You have 4 - 3 = 1 health.
Note that you did not use your armor ability.

Constraints

• n == damage.length
• 1 <= n <= 105
• 0 <= damage[i] <= 105
• 0 <= armor <= 105

Approach and Intuition

When tackling this problem, the goal is to minimize the initial health required for survival by effective use of the armor. Here's a clear breakdown of the approach:

1. Calculate the total damage without any armor, which is simply the cumulative sum of all values in the damage[] array.
2. For each level, compute how effective the armor would be. This is done by considering the actual damage on that level and how much of it can be blocked by the armor. The actual benefit is the lesser of the armor value or the damage at that level.
3. Compute the maximum benefit obtained from using the armor on any given level.
4. Calculate the required starting health by subtracting this maximum benefit from the total damage and then adding one (to ensure the health remains above zero across all levels).

This approach not only ensures that the armor is used optimally (i.e., at the level where it reduces the most damage) but also ensures that the player's health does not drop to zero or below at any level. Through this method, the computation is both efficient and straightforward, addressing the problem directly by focusing on the key variables—total damage and optimal armor use.

Solutions

class Solution {
public:
    long long minimumHealth(vector<int>& damage, int armor) {
        int highestDamage = 0;
        long long sumDamage = 0;
            
        for (int dmg : damage) {
            sumDamage += dmg;
            highestDamage = max(highestDamage, dmg);
        }
    
        return sumDamage - min(armor, highestDamage) + 1;
    }
};