Difficulty: Easy | Acceptance: 42.60% | Paid: No Topics: Array, Greedy
You are entering a competition, and you need to calculate the minimum hours of training required to win.
You are given two integers initialEnergy and initialExperience representing your initial energy and initial experience, respectively.
You are also given two 0-indexed integer arrays energy and experience of length n.
For each opponent i:
- You need strictly more energy than energy[i] to beat them.
- You need strictly more experience than experience[i] to beat them.
- If you beat them, you gain experience[i] experience.
You can train for some number of hours to increase your initial energy or initial experience. You can train for at most one hour at a time, and you can decide to train either energy or experience.
Return the minimum number of hours of training required to win all n competitions.
- Examples
- Constraints
- Greedy Simulation
- Mathematical Formula
Examples
Input: initialEnergy = 5, initialExperience = 3, energy = [1,4,3,2], experience = [2,6,3,1]
Output: 8
Explanation: You can train for 6 hours on energy and 2 hours on experience.
After training, your energy is 11 and experience is 5.
You beat all opponents and win the competition.
Input: initialEnergy = 2, initialExperience = 4, energy = [1], experience = [3]
Output: 0
Explanation: You do not need any training. You beat the opponent with 2 energy and 4 experience.
Constraints
n == energy.length == experience.length
1 <= n <= 100
1 <= initialEnergy, initialExperience <= 100
1 <= energy[i], experience[i] <= 100
Greedy Simulation
Intuition Calculate energy training upfront since we need total energy greater than sum of all opponent energy. For experience, simulate the competition and add training whenever we encounter an opponent we cannot beat.
Steps
- Calculate total energy needed as sum of all energy values plus 1
- Energy training is max(0, totalEnergyNeeded - initialEnergy)
- For experience, iterate through opponents and track current experience
- When current experience is not enough, add training hours
- Return sum of energy and experience training hours
class Solution:
def minNumberOfHours(self, initialEnergy: int, initialExperience: int, energy: list[int], experience: list[int]) -> int:
energy_training = max(0, sum(energy) + 1 - initialEnergy)
exp_training = 0
current_exp = initialExperience
for exp in experience:
if current_exp <= exp:
exp_training += exp + 1 - current_exp
current_exp = exp + 1
current_exp += exp
return energy_training + exp_training
Complexity
- Time: O(n) where n is the number of opponents
- Space: O(1) constant extra space
- Notes: Single pass through arrays with optimal calculation
Mathematical Formula
Intuition Derive the experience training formula using prefix sums. The minimum experience needed at each step is the maximum deficit encountered when comparing required experience against accumulated gains.
Steps
- Calculate energy training as before
- For experience, use prefix sum to track accumulated experience gains
- At each opponent, compute the deficit: experience[i] + 1 - initialExperience - prefixSum
- Take the maximum of all deficits as the required experience training
- Return sum of both training values
class Solution:
def minNumberOfHours(self, initialEnergy: int, initialExperience: int, energy: list[int], experience: list[int]) -> int:
energy_training = max(0, sum(energy) + 1 - initialEnergy)
exp_training = 0
prefix_sum = 0
for exp in experience:
exp_training = max(exp_training, exp + 1 - initialExperience - prefix_sum)
prefix_sum += exp
return energy_training + exp_training
Complexity
- Time: O(n) where n is the number of opponents
- Space: O(1) constant extra space
- Notes: Same complexity as simulation but uses mathematical insight for cleaner code