algoadvance

Leetcode 2383. Minimum Hours of Training to Win a Competition

Problem Statement

Leetcode Problem 2383: Minimum Hours of Training to Win a Competition

You are given two integers initialEnergy and initialExperience. You are also given two integer arrays energy and experience, both of length n.

You are competing in n training sessions where the i-th session has:

You can defeat the opponent in the i-th session if you both:

  1. Have enough energy to pass through the session, i.e., initialEnergy must be greater than energy[i].
  2. Have enough experience to defeat the opponent, i.e., initialExperience must be greater than experience[i].

Each time you defeat an opponent, your experience increases by experience[i]. Also, you can choose to train to increase your experience by 1 unit in one hour, and you can increase your energy by 1 unit in one hour as well.

Return the minimum number of hours of training needed to defeat all the opponents in the n training sessions.

Clarifying Questions

  1. What is the range of n?
    • The number of training sessions n can be up to 1000.
  2. Can the values inside the energy and experience arrays be negative or zero?
    • No, the values inside energy and experience will be positive integers.
  3. Can initialEnergy or initialExperience be zero or negative?
    • No, both initialEnergy and initialExperience will be positive integers.
  4. Is there a maximum limit for initialEnergy and initialExperience?
    • Let’s consider the typical constraints (e.g., within the range of 10^5).

Strategy

The strategy to solve this problem involves:

  1. Iterating through each training session and checking if we need to train more energy or experience.
  2. Keeping track of how much extra energy or experience is needed to defeat the current opponent.
  3. Summing the total hours of training required across all sessions.

Code

#include <vector>
#include <algorithm>

class Solution {
public:
    int minNumberOfHours(int initialEnergy, int initialExperience, std::vector<int>& energy, std::vector<int>& experience) {
        int n = energy.size();
        int requiredEnergy = 0, totalHours = 0;
        
        // Calculate the total energy required to defeat all opponents.
        for (int i = 0; i < n; ++i) {
            requiredEnergy += energy[i];
        }
        
        // If the initial energy is less than required, calculate the additional hours needed.
        if (initialEnergy <= requiredEnergy) {
            totalHours += requiredEnergy - initialEnergy + 1;
        }
        
        // Process each training session.
        for (int i = 0; i < n; ++i) {
            if (initialExperience <= experience[i]) {
                totalHours += experience[i] - initialExperience + 1;
                initialExperience = experience[i] + 1;
            }
            // Simulate defeating the opponent and increasing experience.
            initialExperience += experience[i];
        }
        
        return totalHours;
    }
};

Time Complexity

This solution ensures that you have enough energy and experience to win all training sessions while computing the minimal hours of training required efficiently.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI