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 _theminimum number of training hours required to defeat all _n opponents.

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

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

1
2
3

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

Method 1 – Greedy Simulation

Intuition

To defeat all opponents, you must have strictly more energy and experience than each opponent. For energy, you can train enough to cover the total energy needed. For experience, you may need to train before each opponent if your experience is not enough.

Approach

  1. Calculate the total energy required by summing all opponent energies. If initial energy is less than or equal to this, train to reach one more than the total.
  2. For experience, iterate through each opponent. If your experience is less than or equal to the opponent’s, train to reach one more than theirs before the match.
  3. After each match, update your experience and energy.
  4. Sum all training hours for energy and experience.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
public:
    int minNumberOfHours(int initialEnergy, int initialExperience, vector<int>& energy, vector<int>& experience) {
        int n = energy.size();
        int needEnergy = max(0, accumulate(energy.begin(), energy.end(), 0) + 1 - initialEnergy);
        int needExp = 0, curExp = initialExperience;
        for (int i = 0; i < n; ++i) {
            if (curExp <= experience[i]) {
                needExp += experience[i] + 1 - curExp;
                curExp = experience[i] + 1;
            }
            curExp += experience[i];
        }
        return needEnergy + needExp;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

func minNumberOfHours(initialEnergy int, initialExperience int, energy []int, experience []int) int {
    needEnergy := 0
    sumEnergy := 0
    for _, e := range energy {
        sumEnergy += e
    }
    if initialEnergy <= sumEnergy {
        needEnergy = sumEnergy + 1 - initialEnergy
    }
    needExp := 0
    curExp := initialExperience
    for i := 0; i < len(experience); i++ {
        if curExp <= experience[i] {
            needExp += experience[i] + 1 - curExp
            curExp = experience[i] + 1
        }
        curExp += experience[i]
    }
    return needEnergy + needExp
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
    public int minNumberOfHours(int initialEnergy, int initialExperience, int[] energy, int[] experience) {
        int needEnergy = Math.max(0, Arrays.stream(energy).sum() + 1 - initialEnergy);
        int needExp = 0, curExp = initialExperience;
        for (int i = 0; i < experience.length; i++) {
            if (curExp <= experience[i]) {
                needExp += experience[i] + 1 - curExp;
                curExp = experience[i] + 1;
            }
            curExp += experience[i];
        }
        return needEnergy + needExp;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
    fun minNumberOfHours(initialEnergy: Int, initialExperience: Int, energy: IntArray, experience: IntArray): Int {
        val needEnergy = maxOf(0, energy.sum() + 1 - initialEnergy)
        var needExp = 0
        var curExp = initialExperience
        for (i in experience.indices) {
            if (curExp <= experience[i]) {
                needExp += experience[i] + 1 - curExp
                curExp = experience[i] + 1
            }
            curExp += experience[i]
        }
        return needEnergy + needExp
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

def min_number_of_hours(initial_energy: int, initial_experience: int, energy: list[int], experience: list[int]) -> int:
    need_energy = max(0, sum(energy) + 1 - initial_energy)
    need_exp = 0
    cur_exp = initial_experience
    for exp in experience:
        if cur_exp <= exp:
            need_exp += exp + 1 - cur_exp
            cur_exp = exp + 1
        cur_exp += exp
    return need_energy + need_exp
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

impl Solution {
    pub fn min_number_of_hours(initial_energy: i32, initial_experience: i32, energy: Vec<i32>, experience: Vec<i32>) -> i32 {
        let need_energy = (energy.iter().sum::<i32>() + 1 - initial_energy).max(0);
        let mut need_exp = 0;
        let mut cur_exp = initial_experience;
        for &exp in &experience {
            if cur_exp <= exp {
                need_exp += exp + 1 - cur_exp;
                cur_exp = exp + 1;
            }
            cur_exp += exp;
        }
        need_energy + need_exp
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
    minNumberOfHours(initialEnergy: number, initialExperience: number, energy: number[], experience: number[]): number {
        let needEnergy = Math.max(0, energy.reduce((a, b) => a + b, 0) + 1 - initialEnergy);
        let needExp = 0, curExp = initialExperience;
        for (let exp of experience) {
            if (curExp <= exp) {
                needExp += exp + 1 - curExp;
                curExp = exp + 1;
            }
            curExp += exp;
        }
        return needEnergy + needExp;
    }
}

Complexity

  • ⏰ Time complexity: O(n), where n is the number of opponents. We iterate through the arrays once.
  • 🧺 Space complexity: O(1), only a few variables are used for tracking the answer.