FastPrep
Problem · Array

Minimum Starting Health to Win the Game

Learn this problem
● EasyAmazon logoAmazonNEW GRADOA
See Amazon hiring insights

Problem statement

Note - Similar to LC 2214

In Amazon Prime Games, a player needs to pass n rounds sequentially. The rules are as follows:

  • The player loses power[i] health to complete round i.
  • The player's health must always be greater than 0 at all times.
  • The player can use armor in only one round, which prevents damage of min(armor, power[i]) for that round.

    • You need to determine the minimum starting health required for the player to win the game.

    Thank you so much, Spike! 😊

    Function

    minimumStartingHealth(power: int[], armor: int) → int

    Examples

    Example 1

    power = [1, 2, 6, 7]armor = 5return = 12

    Starting health = 12
    Round 1: Health = 12 - 1 = 11
    Round 2: Health = 11 - 2 = 9
    Round 3: Health = 9 - (6 - 5) = 8
    Round 4: Health = 8 - 7 = 1
    The minimum starting health required to win the game is 12.

    Example 2

    power = [1, 2, 3]armor = 1return = 6

    Starting health = 6
    Round 1: Health = 6 - 1 + 1 (armor) = 6
    Round 2: Health = 6 - 2 = 4
    Round 3: Health = 4 - 3 = 1
    The minimum starting health required to win the game is 6.

    Constraints

  • The first line contains an integer n (1 ≤ n ≤ 10^5) — the number of rounds.
  • The next n lines contain integers power[i] (1 ≤ power[i] ≤ 10^9) — the health cost to complete each round.
  • The last line contains an integer armor (1 ≤ armor ≤ 10^9) — the maximum amount of health that may be returned by armor.

    • More Amazon problems

    drafts saved locally
    public int minimumStartingHealth(int[] power, int armor) {
  // write your code here
}
    power[1, 2, 6, 7]
    armor5
    expected12
    checking account