FastPrep
Problem · Array

Minimum Starting Health to Win the Game

● EasyAmazonNEW GRADOA
See Amazon hiring insights

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! 😊

    Examples
    01 · Example 1
    power = [1, 2, 6, 7]
armor = 5
return = 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.

    02 · Example 2
    power = [1, 2, 3]
armor = 1
return = 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
    sign in to submit