Minimum Hours of Training to Win a Competition

You are entering a competition, and are given two positive integers initialEnergy and initialExperience denoting your initial energy and initial experience respectively.

You are also given two 0-indexed integer arrays energy and experience, both of length n.

You will face n opponents in order. The energy and experience of the i^th opponent is denoted by energy[i] and experience[i] respectively. When you face an opponent, you need to have both strictly greater experience and energy to defeat them and move to the next opponent if available.

Defeating the i^th opponent increases your experience by experience[i], but decreases your energy by energy[i].

Before starting the competition, you can train for some number of hours. After each hour of training, you can either choose to increase your initial experience by one, or increase your initial energy by one.

Return the minimum number of training hours required to defeat all n opponents.

Example 1
InputinitialEnergy = 5, initialExperience = 3, energy = [1,4,3,2], experience = [2,6,3,1]
Output8
Training 6 hours for energy and 2 hours for experience is sufficient to defeat all opponents in order, and no smaller total works.
Example 2
InputinitialEnergy = 2, initialExperience = 4, energy = [1], experience = [3]
Output0
The initial energy and experience are already strictly greater than the only opponent's values, so no training is needed.

Constraints

  • n == energy.length == experience.length
  • 1 <= n <= 100
  • 1 <= initialEnergy, initialExperience, energy[i], experience[i] <= 100

Asked at 1 companies

</>

Your Solution

(Ctrl/Cmd + Enter)

Switching Language

Loading template...

Loading...

Sign in to save your progress

AI code evaluation

Get a correctness verdict, missed edge cases, and complexity analysis of your solution.

Sign in to evaluate