Minimum Hours of Training to Win a Competition

Minimum Hours of Training to Win a Competition - Problem

Array Greedy Easy

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 i-th 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 i-th 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.

Input & Output

Example 1 — Basic Training Need

$ Input: initialEnergy = 5, initialExperience = 3, energy = [1,4,3,2], experience = [2,6,3,1]

› Output: 8

💡 Note: Need experience > 2 for first opponent (have 3, OK). Need energy > 4 for second opponent after losing 1 energy, so need 1 more. Need experience > 6 for second opponent after gaining 2 experience (have 5), so need 2 more. Continue simulation to get total 8 training hours.

Example 2 — No Training Needed

$ Input: initialEnergy = 20, initialExperience = 15, energy = [1,2,3], experience = [1,2,3]

› Output: 0

💡 Note: Already have enough energy and experience to defeat all opponents without any training.

Example 3 — Single Opponent

$ Input: initialEnergy = 1, initialExperience = 1, energy = [1], experience = [1]

› Output: 2

💡 Note: Need energy > 1 and experience > 1. Currently have energy=1, experience=1, so need 1 hour each for energy and experience training.

Constraints

n == energy.length == experience.length
1 ≤ n ≤ 100
1 ≤ initialEnergy, initialExperience ≤ 100
1 ≤ energy[i], experience[i] ≤ 100

Visualization

Tap to expand

Asked in

a Amazon 15 M Microsoft 8

The key insight is to simulate the competition once and calculate training needs on-demand. When we encounter an opponent we can't defeat, we calculate exactly how much training is needed. Best approach is greedy simulation in O(n) time, O(1) space.

Common Approaches

Approach	Time	Space	Notes
✓ Greedy Simulation	O(n)	O(1)	Simulate the competition once, calculating minimum requirements as we go
Try All Training Combinations	O(h² × n)	O(1)	Test every possible distribution of training hours between energy and experience

Greedy Simulation — Algorithm Steps

Start with initial stats
For each opponent, check if we can defeat them
If not, calculate minimum training needed
Update stats after each victory

Visualization

Tap to expand

Step-by-Step Walkthrough

Start

Begin with initial energy=5, experience=3

Battle

For each opponent, check if we can win

Train

Add training hours if needed, then fight

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(int initialEnergy, int initialExperience, int* energy, int* experience, int n) {
    int currentEnergy = initialEnergy;
    int currentExp = initialExperience;
    int trainingHours = 0;
    
    for (int i = 0; i < n; i++) {
        // Check if we need more experience
        if (currentExp <= experience[i]) {
            int needed = experience[i] + 1 - currentExp;
            trainingHours += needed;
            currentExp += needed;
        }
        
        // Check if we need more energy
        if (currentEnergy <= energy[i]) {
            int needed = energy[i] + 1 - currentEnergy;
            trainingHours += needed;
            currentEnergy += needed;
        }
        
        // Fight the opponent
        currentEnergy -= energy[i];
        currentExp += experience[i];
    }
    
    return trainingHours;
}

int main() {
    int initialEnergy, initialExperience;
    scanf("%d", &initialEnergy);
    scanf("%d", &initialExperience);
    
    char line[10000];
    scanf(" %s", line);
    
    int energy[1000], experience[1000], n = 0;
    char* token = strtok(line + 1, ",]");
    while (token != NULL) {
        energy[n++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    scanf(" %s", line);
    int m = 0;
    token = strtok(line + 1, ",]");
    while (token != NULL) {
        experience[m++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    printf("%d\n", solution(initialEnergy, initialExperience, energy, experience, n));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass through all n opponents to simulate battles

✓ Linear Growth

Space Complexity

O(1)

Only using variables to track current energy, experience, and training needed

✓ Linear Space

12.0K Views

Medium Frequency

~15 min Avg. Time

450 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Greedy Simulation — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler