2383. Minimum Hours of Training to Win a Competition
Problem Description
In this competition, you're equipped with two initial resources: energy and experience, which are both positive integers. You'll be contending against n challengers, whose energy and experience levels are listed in two separate arrays named energy and experience, respectively. These arrays are matched in length, representing the sequence of opponents you'll face.
Your goal is to overcome each adversary sequentially. To successfully defeat an adversary, you must possess more energy and more experience than they do. When you overcome an opponent, it will cost you some of your energy (specifically, energy[i]), but you'll gain experience (precisely, experience[i]). There's a catch, though; if your current levels of energy or experience are not sufficient to beat an opponent, you have the option to train.
Training can be done as much as needed before the competition starts. Each hour of training allows you to boost either your energy or your experience by one unit. The problem is to determine the minimal number of hours you need to train to guarantee victory over all n opponents.
Intuition
To solve this problem, we need to ensure that before each fight, our energy and experience exceed those of the current opponent. To achieve this, we may need to engage in some preemptive training.
The intuition behind the solution involves iterating over each opponent and checking if our current energy and experience is sufficient to win. For energy, if we have less or equal energy compared to the current opponent's energy, we must train until our energy is greater by at least one. Similarly, for experience, if our experience is less or equal to that of the current opponent, we train until our experience exceeds the opponent's by at least one.
After ensuring we can defeat the opponent, we then engage in the battle, which results in a decrease in energy by energy[i] and an increase in experience by experience[i]. We continue this process, battle by battle, keeping track of the total hours spent training, until we are capable of defeating all opponents.
Thus, the solution is a simple simulation that accumulates the total number of training hours necessary as we iterate over the array of opponents.
Learn more about Greedy patterns.
Which algorithm should you use to find a node that is close to the root of the tree?
Solution Approach
The implementation provided is straightforward and does not use complex data structures or algorithms. It simply iterates through the two input arrays - energy and experience - and directly modifies the initialEnergy and initialExperience variables while keeping track of the additional training hours needed with the ans variable. The procedural steps can be broken down as follows:
- Initialize
ansto0. This variable will accumulate the total hours of training needed. - Loop through the
energyandexperiencearrays simultaneously using Python's built-inzipfunction. This allows us to examine the energy and experience of each opponent in the sequence they are encountered. - For each opponent, compare
initialEnergywith the opponent's energy (a):- If
initialEnergyis less than or equal toa, calculate the difference between the opponent's energy and yours, add one to it (to ensure it's strictly greater), and add that toans. - Then, set
initialEnergyto the opponent's energy plus one for the same reason.
- If
- Perform a similar operation for experience. Compare
initialExperiencewith the opponent's experience (b):- If
initialExperienceis less than or equal tob, calculate the difference, add one, and incrementanswith this value. - Update
initialExperienceto the opponent's experience plus one.
- If
- After adjusting for any needed training, simulate the battle by decreasing
initialEnergybya(the opponent's energy) and increasinginitialExperiencebyb(the opponent's experience). - Repeat steps 3 to 5 for each opponent until you have iterated through all elements of
energyandexperiencearrays. - Once all opponents have been considered, return
answhich now contains the minimum number of training hours required to defeat all opponents.
By using simple conditional checks and updating variables on-the-fly, this approach simulates each match's outcome while accommodating any necessary training beforehand. No extra space is required beyond the function's parameters and local variables, making the space complexity O(1). The time complexity is O(n), where n is the number of opponents, since we need to perform a constant amount of work per opponent.
Which type of traversal does breadth first search do?
Example Walkthrough
Assume our initial energy is 15 and our initial experience is 10. We face 3 opponents with the following profiles:
- Opponent 1: Energy = 5, Experience = 3
- Opponent 2: Energy = 14, Experience = 8
- Opponent 3: Energy = 10, Experience = 15
We start by comparing our energy and experience to those of Opponent 1.
-
We have 15 energy and 10 experience, which is more than Opponent 1, so no training is needed. After defeating Opponent 1, we subtract their energy from ours and add their experience to ours. Our new energy and experience are 10 (15 - 5) and 13 (10 + 3), respectively.
-
Our energy is weaker than Opponent 2 (10 < 14), so we need training. We train for 5 hours to raise our energy to 15 (10 + 5). We have 15 energy and 13 experience facing Opponent 2, so no experience training is needed. After the match, our energy is 1 (15 - 14) and our experience is 21 (13 + 8).
-
Facing Opponent 3, our energy is low. We must train for 10 hours to get to 11 energy (1 + 10). However, our experience (21) is already higher than Opponent 3’s, so no training for experience is needed. After this match, we end with 1 energy (11 - 10) and 36 experience (21 + 15).
Through this process, we trained for 15 hours (5 hours for energy against Opponent 2 and 10 hours for energy against Opponent 3), ensuring victory against all opponents. This example confirms the strategy of checking each opponent's energy and experience, training as needed, and then recalculating our stats after each battle to be prepared for the next one.
Solution Implementation
1from typing import List
2
3class Solution:
4 def minNumberOfHours(
5 self,
6 initial_energy: int,
7 initial_experience: int,
8 energy_required: List[int],
9 experience_gained: List[int],
10 ) -> int:
11 # Initialize the number of hours the hero needs to train to 0.
12 total_hours_needed = 0
13
14 # Iterate over the battles the hero needs to fight.
15 for required_energy, gained_experience in zip(energy_required, experience_gained):
16 # Check if the hero's current energy is less than or equal to the required energy for the battle.
17 if initial_energy <= required_energy:
18 # Calculate the energy shortfall and increment hours needed to at least one more than required.
19 energy_shortfall = required_energy - initial_energy + 1
20 total_hours_needed += energy_shortfall
21 # Update the hero's energy level after training.
22 initial_energy += energy_shortfall
23
24 # Check if the hero's current experience is less than or equal to the experience of the enemy.
25 if initial_experience <= gained_experience:
26 # Calculate the experience shortfall and increment hours needed to at least one more than the enemy's.
27 experience_shortfall = gained_experience - initial_experience + 1
28 total_hours_needed += experience_shortfall
29 # Update the hero's experience level after training.
30 initial_experience += experience_shortfall
31
32 # Deduct the energy used for this battle from the hero's current energy.
33 initial_energy -= required_energy
34 # Add the experience gained from this battle to the hero's experience.
35 initial_experience += gained_experience
36
37 # Return the total number of hours the hero needs to train to be able to defeat all enemies.
38 return total_hours_needed
391class Solution {
2
3 public int minNumberOfHours(int initialEnergy, int initialExperience, int[] energyNeeded, int[] experienceEarned) {
4 int additionalHours = 0; // Stores the total additional hours of training required.
5
6 // Loop through each training session
7 for (int i = 0; i < energyNeeded.length; ++i) {
8 int requiredEnergy = energyNeeded[i]; // Energy needed for the current training session.
9 int requiredExperience = experienceEarned[i]; // Experience earned from the current training session.
10
11 // If not enough energy, calculate and add the necessary training hours needed to gain energy.
12 if (initialEnergy <= requiredEnergy) {
13 additionalHours += requiredEnergy - initialEnergy + 1;
14 initialEnergy = requiredEnergy + 1; // Update initialEnergy to the new value after training.
15 }
16
17 // If not enough experience, calculate and add the necessary training hours needed to gain experience.
18 if (initialExperience <= requiredExperience) {
19 additionalHours += requiredExperience - initialExperience + 1;
20 initialExperience = requiredExperience + 1; // Update initialExperience to the new value after training.
21 }
22
23 // Deduct the used energy from the initialEnergy.
24 initialEnergy -= requiredEnergy;
25 // Add the gained experience to the initialExperience.
26 initialExperience += requiredExperience;
27 }
28
29 // Return the total additional hours of training required.
30 return additionalHours;
31 }
32}
331class Solution {
2public:
3 int minNumberOfHours(int initialEnergy, int initialExperience, vector<int>& energyRequired, vector<int>& experienceGained) {
4 int additionalHours = 0; // Store the total additional hours needed
5
6 // Iterating through each training session
7 for (int i = 0; i < energyRequired.size(); ++i) {
8 int energyNeeded = energyRequired[i]; // Energy needed for this session
9 int experienceNeeded = experienceGained[i]; // Experience to be gained from this session
10
11 // If initial energy is not enough, train to get just enough energy plus one
12 if (initialEnergy <= energyNeeded) {
13 additionalHours += energyNeeded - initialEnergy + 1; // Increment additional hours by the shortfall in energy plus one
14 initialEnergy = energyNeeded + 1; // Update energy to the new level after training
15 }
16
17 // If initial experience is not enough, train to get just enough experience plus one
18 if (initialExperience <= experienceNeeded) {
19 additionalHours += experienceNeeded - initialExperience + 1; // Increment additional hours by the shortfall in experience plus one
20 initialExperience = experienceNeeded + 1; // Update experience to the new level after training
21 }
22
23 // After successful training or if already sufficient, reduce energy and increase experience for the current session
24 initialEnergy -= energyNeeded; // Deduct the energy used for this session
25 initialExperience += experienceNeeded; // Add the experience gained from this session
26 }
27
28 // Return the total additional hours of training needed to be ready for all sessions
29 return additionalHours;
30 }
31};
321/**
2 * Calculate the minimum number of training hours needed to beat all opponents.
3 *
4 * @param initialEnergy - The starting energy level of the player.
5 * @param initialExperience - The starting experience points of the player.
6 * @param energy - The array of energy points required to beat each opponent.
7 * @param experience - The array of experience points the player gains after beating each opponent.
8 * @returns The minimum number of training hours required.
9 */
10function minNumberOfHours(
11 initialEnergy: number,
12 initialExperience: number,
13 energy: number[],
14 experience: number[]
15): number {
16 const numberOfOpponents = energy.length;
17 let totalTrainingHours = 0;
18
19 for (let i = 0; i < numberOfOpponents; i++) {
20 const opponentEnergy = energy[i];
21 const opponentExperience = experience[i];
22
23 // Check if the player's energy is less than or equal to the opponent's requirement
24 if (initialEnergy <= opponentEnergy) {
25 const energyShortage = opponentEnergy - initialEnergy + 1;
26 totalTrainingHours += energyShortage;
27 initialEnergy += energyShortage; // Increase player's energy to beat the opponent
28 }
29
30 // Check if the player's experience is less than or equal to the opponent's
31 if (initialExperience <= opponentExperience) {
32 const experienceShortage = opponentExperience - initialExperience + 1;
33 totalTrainingHours += experienceShortage;
34 initialExperience += experienceShortage; // Increase player's experience to beat the opponent
35 }
36
37 // After defeating the opponent, player spends energy and gains experience
38 initialEnergy -= opponentEnergy;
39 initialExperience += opponentExperience;
40 }
41
42 return totalTrainingHours;
43}
44In a binary min heap, the maximum element can be found in:
Time and Space Complexity
Time Complexity
The time complexity of the given code is primarily determined by the loop that iterates over the two lists energy and experience. Since these lists are traversed in a single pass using zip(), the complexity depends on the length of the lists. Let's denote the length of the lists as n. Therefore, we can conclude that the time complexity is O(n), where n is the number of battles (the length of the lists).
Space Complexity
The given code uses a few variables (ans, initialEnergy, initialExperience) but does not allocate any additional space that grows with the size of the input. The use of zip() does not create a new list but returns an iterator that produces tuples on demand, so it doesn't significantly affect the space complexity. As a result, the space complexity is O(1), which means it is constant and does not depend on the size of the input lists.
Learn more about how to find time and space complexity quickly using problem constraints.
In a binary min heap, the maximum element can be found in:
Recommended Readings
Greedy Introduction iframe width 560 height 315 src https www youtube com embed WTslqPbj7I title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture web share allowfullscreen iframe When do we use greedy Greedy algorithms tend to solve optimization problems Typically they will ask you
Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Got a question? Ask the Teaching Assistant anything you don't understand.
Still not clear? Ask in the Forum, Discord or Submit the part you don't understand to our editors.