FastPrepFastPrep
Problem Brief

Minimum Starting Health to Win the Game

NEW GRADOA

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

    1Example 1

    Input
    power = [1, 2, 6, 7], armor = 5
    Output
    12
    Explanation

    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.

    2Example 2

    Input
    power = [1, 2, 3], armor = 1
    Output
    6
    Explanation

    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

    Limits and guarantees your solution can rely on.

  • 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.
    • public int minimumStartingHealth(int[] power, int armor) {
  // write your code here
}
    Input

    power

    [1, 2, 6, 7]

    armor

    5

    Output

    12

    Sign in to submit your solution.