Minimum Hours of Training to Win a Competition
EasyPrompt
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 ith 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 ith 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:
Input: initialEnergy = 5, initialExperience = 3, energy = [1,4,3,2], experience = [2,6,3,1]
Output: 8
Explanation: You can increase your energy to 11 after 6 hours of training, and your experience to 5 after 2 hours of training.
You face the opponents in the following order:
- You have more energy and experience than the 0th opponent so you win.
Your energy becomes 11 - 1 = 10, and your experience becomes 5 + 2 = 7.
- You have more energy and experience than the 1st opponent so you win.
Your energy becomes 10 - 4 = 6, and your experience becomes 7 + 6 = 13.
- You have more energy and experience than the 2nd opponent so you win.
Your energy becomes 6 - 3 = 3, and your experience becomes 13 + 3 = 16.
- You have more energy and experience than the 3rd opponent so you win.
Your energy becomes 3 - 2 = 1, and your experience becomes 16 + 1 = 17.
You did a total of 6 + 2 = 8 hours of training before the competition, so we return 8.
It can be proven that no smaller answer exists.Example 2:
Input: initialEnergy = 2, initialExperience = 4, energy = [1], experience = [3]
Output: 0
Explanation: You do not need any additional energy or experience to win the competition, so we return 0.
Constraints:
n == energy.length == experience.length1 <= n <= 1001 <= initialEnergy, initialExperience, energy[i], experience[i] <= 100
Approaches
3 approaches with complexity analysis and trade-offs.
This approach exhaustively searches for the minimum total training hours. It starts by checking if 0 hours are sufficient, then 1 hour, and so on. For each total number of hours H, it checks every possible distribution of these hours between energy and experience. The first valid distribution found corresponds to the minimum total hours.
Algorithm
- Iterate through the total number of training hours
H, starting from 0. - For each
H, iterate through all possible ways to split it into energy training hoursh_eand experience training hoursh_x(i.e.,h_efrom 0 toH,h_x = H - h_e). - For each pair
(h_e, h_x), simulate the entire competition to check if this amount of training is sufficient. - The simulation function
check(h_e, h_x):- Sets
currentEnergy = initialEnergy + h_eandcurrentExperience = initialExperience + h_x. - Iterates through all
nopponents. - For opponent
i, it checks ifcurrentEnergy > energy[i]andcurrentExperience > experience[i]. - If the condition fails, the simulation returns
false. - If it succeeds, it updates
currentEnergy -= energy[i]andcurrentExperience += experience[i]. - If the loop finishes, the simulation returns
true.
- Sets
- The first value of
Hfor which the simulation returnstrueis the minimum required hours, so we return it.
Walkthrough
The core idea is to brute-force the answer. We are looking for the minimum total_hours. We can test total_hours = 0, 1, 2, ... in increasing order. For a given total_hours, we need to decide how many hours go to energy (h_e) and how many to experience (h_x), where h_e + h_x = total_hours. We can try all possibilities: (h_e=0, h_x=H), (h_e=1, h_x=H-1), ..., (h_e=H, h_x=0). For each combination, we run a full simulation of the competition. If we can defeat all opponents, we have found our answer. Since we are checking total_hours in increasing order, the first success guarantees the minimum.
class Solution { public int minNumberOfHours(int initialEnergy, int initialExperience, int[] energy, int[] experience) { for (int totalHours = 0; ; totalHours++) { for (int energyHours = 0; energyHours <= totalHours; energyHours++) { int experienceHours = totalHours - energyHours; if (canWin(initialEnergy + energyHours, initialExperience + experienceHours, energy, experience)) { return totalHours; } } } } private boolean canWin(long currentEnergy, long currentExperience, int[] energy, int[] experience) { for (int i = 0; i < energy.length; i++) { if (currentEnergy <= energy[i] || currentExperience <= experience[i]) { return false; } currentEnergy -= energy[i]; currentExperience += experience[i]; } return true; }}Complexity
Time
O(S^2 * n), where `S` is the minimum required training hours and `n` is the number of opponents. Given the constraints, `S` can be up to ~10000, making this approach too slow.
Space
O(1) - We only use a few variables to store the current state during the simulation.
Trade-offs
Pros
Conceptually simple and easy to understand.
Cons
Extremely inefficient and will result in a 'Time Limit Exceeded' error for the given constraints.
The search space for the total hours can be very large.
This approach improves upon the naive brute force by recognizing that the energy and experience requirements are independent. We can calculate the minimum training for energy directly in one pass. Then, we only need to brute-force the training hours for experience, which has a much smaller search space.
Algorithm
- Decouple the problem: Realize that the training for energy and experience are independent. The total minimum hours is the sum of the minimum hours needed for energy and the minimum hours needed for experience.
- Calculate Energy Training: The total energy consumed is
sum(energy). To survive, the initial energy must be at leastsum(energy) + 1. Calculaterequired_energy = sum(energy) + 1. The training hours for energy ismax(0, required_energy - initialEnergy). - Calculate Experience Training (Brute Force): Find the minimum required experience training
h_xby searching.- Iterate
h_xfrom 0 upwards. - For each
h_x, run a simulation withinitialExperience + h_xto see if it's enough to defeat all opponents (based on experience only). - The first
h_xthat succeeds is the minimum.
- Iterate
- Combine Results: Return the sum of energy training hours and experience training hours.
Walkthrough
We can solve for the minimum energy and experience training separately.
Energy: To defeat all opponents, our energy must be greater than the opponent's energy at every step. This is guaranteed if our starting energy is greater than the total energy we will lose. The total energy lost is sum(energy). To be strictly greater, we need at least 1 energy point left at the end. So, the target starting energy is sum(energy) + 1. The required training is max(0, (sum(energy) + 1) - initialEnergy).
Experience: For experience, we can find the minimum required training hours h_x by testing h_x = 0, 1, 2, ... and for each value, checking if it's sufficient. The check involves a simulation where we only consider the experience values.
The total hours is the sum of the hours from these two parts.
class Solution { public int minNumberOfHours(int initialEnergy, int initialExperience, int[] energy, int[] experience) { // Calculate required energy training long totalEnergyRequired = 1; for (int e : energy) { totalEnergyRequired += e; } int energyHours = (int) Math.max(0, totalEnergyRequired - initialEnergy); // Brute-force required experience training int experienceHours = 0; while (true) { if (canWinExperience(initialExperience + experienceHours, experience)) { break; } experienceHours++; } return energyHours + experienceHours; } private boolean canWinExperience(long currentExperience, int[] experience) { for (int exp : experience) { if (currentExperience <= exp) { return false; } currentExperience += exp; } return true; }}Complexity
Time
O(n + M * n), where `n` is the number of opponents and `M` is the minimum required experience training. Since `M` is at most 100, this is effectively O(n).
Space
O(1) - Constant extra space is used.
Trade-offs
Pros
Much more efficient than the full brute-force approach.
Correctly identifies the independence of the two subproblems.
Cons
The brute-force search for experience training is still suboptimal, involving a nested loop structure.
This is the most efficient approach. It calculates the required training for energy and experience independently. The energy requirement is calculated by summing up all opponent energies. The experience requirement is calculated greedily in a single pass. We iterate through the opponents, and whenever our current experience is insufficient, we add just enough training hours to defeat the current opponent before moving to the next.
Algorithm
- Decouple the problem: As with the previous approach, solve for energy and experience training independently.
- Calculate Energy Training: Calculate the total energy needed by summing up the
energyarray. The required starting energy issum(energy) + 1. The training hours for energy ismax(0, (sum(energy) + 1) - initialEnergy). - Calculate Experience Training (Greedy): Simulate the competition in a single pass.
- Initialize
hours_experience = 0andcurrent_experience = initialExperience. - Iterate through each opponent
i. - If
current_experience <= experience[i], we need to train. Calculate theneededhours asexperience[i] - current_experience + 1. - Add
neededtohours_experienceand also tocurrent_experience. - After the check (and potential training), update
current_experienceby addingexperience[i].
- Initialize
- Combine Results: The total minimum hours is
hours_energy + hours_experience.
Walkthrough
This optimal solution calculates the required training hours for energy and experience separately in linear time.
Energy Training: The logic is the same as the optimized brute-force approach. We need a starting energy of at least sum(energy) + 1. This requires max(0, (sum(energy) + 1) - initialEnergy) hours of training.
Experience Training: Instead of brute-forcing, we can use a greedy strategy. We simulate the fights and keep track of our current experience. When we encounter an opponent we can't beat (i.e., currentExperience <= opponentExperience), we calculate the exact number of training hours needed to overcome this specific opponent (opponentExperience - currentExperience + 1), add it to our total training hours, and update our current experience accordingly. Then we proceed to the next fight. This ensures we only train the bare minimum required at each step, leading to the overall minimum.
class Solution { public int minNumberOfHours(int initialEnergy, int initialExperience, int[] energy, int[] experience) { int n = energy.length; long totalEnergyRequired = 0; for (int e : energy) { totalEnergyRequired += e; } int trainingHours = 0; if (initialEnergy <= totalEnergyRequired) { trainingHours += (totalEnergyRequired - initialEnergy + 1); } long currentExperience = initialExperience; for (int i = 0; i < n; i++) { if (currentExperience <= experience[i]) { int needed = experience[i] - (int)currentExperience + 1; trainingHours += needed; currentExperience += needed; } currentExperience += experience[i]; } return trainingHours; }}Complexity
Time
O(n) - We iterate through the `energy` and `experience` arrays once. This is linear in the number of opponents.
Space
O(1) - Only a few variables are used for calculations, regardless of the input size.
Trade-offs
Pros
Optimal time complexity of O(n).
Optimal space complexity of O(1).
Simple, single-pass logic that is easy to implement and understand.
Cons
There are no significant cons for this approach as it is optimal for the given problem constraints.
Solutions
Solution
class Solution {public int minNumberOfHours(int initialEnergy, int initialExperience, int[] energy, int[] experience) { int ans = 0; for (int i = 0; i < energy.length; ++i) { int a = energy[i], b = experience[i]; if (initialEnergy <= a) { ans += a - initialEnergy + 1; initialEnergy = a + 1; } if (initialExperience <= b) { ans += b - initialExperience + 1; initialExperience = b + 1; } initialEnergy -= a; initialExperience += b; } return ans; }}class Solution {public: int minNumberOfHours(int initialEnergy, int initialExperience, vector<int> &energy, vector<int> &experience) { int ans = 0; for (int i = 0; i < energy.size(); ++i) { int a = energy[i], b = experience[i]; if (initialEnergy <= a) { ans += a - initialEnergy + 1; initialEnergy = a + 1; } if (initialExperience <= b) { ans += b - initialExperience + 1; initialExperience = b + 1; } initialEnergy -= a; initialExperience += b; } return ans; }};class Solution: def minNumberOfHours(self, initialEnergy: int, initialExperience: int, energy: List[int], experience: List[int], ) -> int: ans = 0 for a, b in zip(energy, experience): if initialEnergy <= a: ans += a - initialEnergy + 1 initialEnergy = a + 1 if initialExperience <= b: ans += b - initialExperience + 1 initialExperience = b + 1 initialEnergy -= a initialExperience += b return ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.