We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Minimum Health to Beat Game

Number: 2354

Difficulty: Medium

Paid? Yes

Companies: Amazon

Problem Description

You are given an array called damage where damage[i] is the health lost when completing the ith level of a game. In addition, you have an armor ability that can be used at most once to reduce the damage taken by up to an integer value armor (i.e. it reduces damage on that level by min(damage[i], armor)). The levels must be completed in order and your health must always remain greater than 0. The goal is to determine the minimum starting health required to beat the game.

Key Insights

  • The total damage without using armor is the sum of the damage array.
  • Using armor on a level reduces the effective damage taken at that level by min(damage[i], armor).
  • To minimize the required starting health, use the armor ability on the level that yields the maximum possible damage reduction.
  • The answer is therefore (total damage - maximum damage reduction achieved by using armor) + 1.

Space and Time Complexity

Time Complexity: O(n), where n is the number of levels, since we scan through the damage array once. Space Complexity: O(1), as only a few additional variables are used.

Solution

We first compute the total damage over all levels. Then we find the best level to use the armor by considering the effective protection (min(damage[i], armor)) at each level and keeping track of the maximum reduction achievable. Finally, since the health must remain greater than 0 after all damage, the minimum starting health required is total damage minus the best damage reduction, plus 1.

Code Solutions

def minimumHealth(damage, armor):
    # Calculate total damage if armor is never applied.
    total_damage = sum(damage)
    # Track the best reduction achievable using armor in one level.
    max_protection = 0
    for dmg in damage:
        # The effective reduction is the minimum between the level damage and armor.
        max_protection = max(max_protection, min(dmg, armor))
    # The minimum starting health is total damage minus the best reduction plus 1.
    return total_damage - max_protection + 1

# Example usage:
print(minimumHealth([2, 7, 4, 3], 4))  # Expected output: 13
print(minimumHealth([2, 5, 3, 4], 7))  # Expected output: 10
print(minimumHealth([3, 3, 3], 0))     # Expected output: 10
← Back to All Questions