{x}
blog image

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 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.length
  • 1 <= n <= 100
  • 1 <= initialEnergy, initialExperience, energy[i], experience[i] <= 100

Solution Explanation: Minimum Hours of Training to Win a Competition

This problem involves determining the minimum training hours needed to win a competition against a series of opponents. Each opponent has energy and experience levels. To defeat an opponent, your energy and experience must strictly exceed theirs. Defeating an opponent increases your experience but decreases your energy. Before the competition, you can train to increase either your energy or experience.

Approach: Greedy Simulation

The most efficient approach is a greedy simulation. We iterate through the opponents, and for each opponent:

  1. Check Energy: If your current energy is less than or equal to the opponent's energy, you need to train to increase your energy. The minimum training needed is opponent's energy + 1 - your current energy. We update your current energy to be one more than the opponent's energy to guarantee victory.

  2. Check Experience: Similarly, if your current experience is less than or equal to the opponent's experience, you need to train to increase your experience. The minimum training needed is opponent's experience + 1 - your current experience. We update your current experience to be one more than the opponent's experience.

  3. Update Stats: After the training (if any), you defeat the opponent. This decreases your energy by the opponent's energy and increases your experience by the opponent's experience.

  4. Repeat: We repeat steps 1-3 for each opponent.

Finally, the total training hours is the sum of training hours from each opponent's encounter.

Time and Space Complexity

  • Time Complexity: O(n), where n is the number of opponents. We iterate through the opponents once.
  • Space Complexity: O(1). We only use a few variables to store the current energy, experience, and training hours. We don't use any data structures that scale with the input size.

Code Implementations

The following code snippets demonstrate the solution in various programming languages. The core logic remains consistent across all implementations.

Python:

class Solution:
    def minNumberOfHours(self, initialEnergy: int, initialExperience: int, energy: List[int], experience: List[int]) -> int:
        total_hours = 0
        current_energy = initialEnergy
        current_experience = initialExperience
        
        for i in range(len(energy)):
            opponent_energy = energy[i]
            opponent_experience = experience[i]
            
            if current_energy <= opponent_energy:
                hours_needed = opponent_energy + 1 - current_energy
                total_hours += hours_needed
                current_energy += hours_needed
            
            if current_experience <= opponent_experience:
                hours_needed = opponent_experience + 1 - current_experience
                total_hours += hours_needed
                current_experience += hours_needed
            
            current_energy -= opponent_energy
            current_experience += opponent_experience
            
        return total_hours

Java:

class Solution {
    public int minNumberOfHours(int initialEnergy, int initialExperience, int[] energy, int[] experience) {
        int totalHours = 0;
        int currentEnergy = initialEnergy;
        int currentExperience = initialExperience;
 
        for (int i = 0; i < energy.length; i++) {
            int opponentEnergy = energy[i];
            int opponentExperience = experience[i];
 
            if (currentEnergy <= opponentEnergy) {
                int hoursNeeded = opponentEnergy + 1 - currentEnergy;
                totalHours += hoursNeeded;
                currentEnergy += hoursNeeded;
            }
 
            if (currentExperience <= opponentExperience) {
                int hoursNeeded = opponentExperience + 1 - currentExperience;
                totalHours += hoursNeeded;
                currentExperience += hoursNeeded;
            }
 
            currentEnergy -= opponentEnergy;
            currentExperience += opponentExperience;
        }
 
        return totalHours;
    }
}

C++:

class Solution {
public:
    int minNumberOfHours(int initialEnergy, int initialExperience, vector<int>& energy, vector<int>& experience) {
        int totalHours = 0;
        int currentEnergy = initialEnergy;
        int currentExperience = initialExperience;
 
        for (int i = 0; i < energy.size(); ++i) {
            int opponentEnergy = energy[i];
            int opponentExperience = experience[i];
 
            if (currentEnergy <= opponentEnergy) {
                int hoursNeeded = opponentEnergy + 1 - currentEnergy;
                totalHours += hoursNeeded;
                currentEnergy += hoursNeeded;
            }
 
            if (currentExperience <= opponentExperience) {
                int hoursNeeded = opponentExperience + 1 - currentExperience;
                totalHours += hoursNeeded;
                currentExperience += hoursNeeded;
            }
 
            currentEnergy -= opponentEnergy;
            currentExperience += opponentExperience;
        }
 
        return totalHours;
    }
};

(Other languages like JavaScript, Go, TypeScript, Rust, and C would follow a very similar structure.) The key is the greedy strategy of immediately addressing any energy or experience deficiency before encountering each opponent.