# Minimum Hours of Training to Win a Competition
**Difficulty:** EASY
[External](https://leetcode.com/problems/minimum-hours-of-training-to-win-a-competition)
Canonical: https://scaleengineer.com/dsa/problems/minimum-hours-of-training-to-win-a-competition
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Data structures:** Array
---
## Problem
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`

# Approaches
## Brute Force Search
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.
**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.
**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.
### Explanation
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.

```java
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;
    }
}
```
### 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 hours `h_e` and experience training hours `h_x` (i.e., `h_e` from 0 to `H`, `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_e` and `currentExperience = initialExperience + h_x`.
  - Iterates through all `n` opponents.
  - For opponent `i`, it checks if `currentEnergy > energy[i]` and `currentExperience > experience[i]`.
  - If the condition fails, the simulation returns `false`.
  - If it succeeds, it updates `currentEnergy -= energy[i]` and `currentExperience += experience[i]`.
  - If the loop finishes, the simulation returns `true`.
- The first value of `H` for which the simulation returns `true` is the minimum required hours, so we return it.

## Optimized Brute Force with Decoupling
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.
**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.
**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.
### Explanation
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.

```java
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;
    }
}
```
### 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 least `sum(energy) + 1`. Calculate `required_energy = sum(energy) + 1`. The training hours for energy is `max(0, required_energy - initialEnergy)`.
- **Calculate Experience Training (Brute Force)**: Find the minimum required experience training `h_x` by searching.
  - Iterate `h_x` from 0 upwards.
  - For each `h_x`, run a simulation with `initialExperience + h_x` to see if it's enough to defeat all opponents (based on experience only).
  - The first `h_x` that succeeds is the minimum.
- **Combine Results**: Return the sum of energy training hours and experience training hours.

## Single Pass Greedy Approach
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.
**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.
**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.
### Explanation
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.

```java
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;
    }
}
```
### 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 `energy` array. The required starting energy is `sum(energy) + 1`. The training hours for energy is `max(0, (sum(energy) + 1) - initialEnergy)`.
- **Calculate Experience Training (Greedy)**: Simulate the competition in a single pass.
  - Initialize `hours_experience = 0` and `current_experience = initialExperience`.
  - Iterate through each opponent `i`.
  - If `current_experience <= experience[i]`, we need to train. Calculate the `needed` hours as `experience[i] - current_experience + 1`.
  - Add `needed` to `hours_experience` and also to `current_experience`.
  - After the check (and potential training), update `current_experience` by adding `experience[i]`.
- **Combine Results**: The total minimum hours is `hours_energy + hours_experience`.

# Solutions
### Java

```java
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;
  }
}

```

### CPP

```cpp
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;
  }
};

```

### Python

```python
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 ans

```